java - 动态规划 - 获取网格中从起点到终点的路径数

Question

我有一个矩阵，一个起点和一个终点，我想计算一个矩阵，其中每个矩阵[i][j] 表示从起点到终点的路径数，这些路径通过 (i, j) 位置。

我的解决方案正确计算了从起点到终点的路径总数(存储在 matrix[startx][starty] 或 matrix[endx][endy] 中的值)，但并非所有其他值都是正确的。

你有什么建议吗？

我的代码如下:

private static long solve() {
    board[startx][starty] = 1; 

    for (int i = endx; i <= startx; i++) { 
        for (int j = endy; j >= starty; j--) { 
                if (i > 0 && j < board[i].length - 1)
                    board[i][j] += board[i - 1][j] + board[i][j + 1];
                else if (i > 0)
                    board[i][j] += board[i - 1][j];
                else if (j < tablero[i].length - 1)
                    board[i][j] += board[i][j + 1];
        }
    }


    for(int j = starty + 1; j < endy; j++) {
            board[endx][j] = board[endx + 1][j] + 
                                  board[endx][j - 1];
    }

    for(int i = endx + 1; i < startx; i++) {
            board[i][endy] = board[i + 1][endy] + 
                board[i][endy - 1]);
    }

    board[endx][endy] = board[endx][endy - 1] + 
                                    board[endx + 1][endy]);


    return board[startx][starty];
}

谢谢。

Answer 1

难道你不只是从这样的事情开始吗:

[[0,0,0,0,0,0]
,[0,0,1,0,0,0]
,[0,0,1,0,0,0]
,[0,0,1,1,1,0]
,[0,0,0,0,0,0]
,[0,0,0,0,0,0]]

然后 M[i][j] = M[i-1][j] + M[i][j-1] ?

[[0,0,0,0,0,0]
,[0,0,1,3,6,0]
,[0,0,1,2,3,0]
,[0,0,1,1,1,0]
,[0,0,0,0,0,0]
,[0,0,0,0,0,0]]