动态编程 - 从起点到终点获取网格中的路径数

Question

我有一个矩阵，一个起点和一个终点，我想计算一个矩阵，其中每个矩阵[i] [j]表示数字从（i，j）位置开始到结束点的路径。

我的解决方案正确计算从起点到终点的路径总数（存储在矩阵[startx] [starty]或矩阵[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]]