動態編程 - 從起點到終點獲取網格中的路徑數

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]]