1.題目
一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為 “Start” ），
機器人每次只能向下或者向右移動一步，機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ），
問總共有多少條不同的路徑？
示例 1：
輸入：m = 3, n = 7
輸出：28示例 2：
輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角，
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下示例 3：
輸入：m = 7, n = 3
輸出：28示例 4：
輸入：m = 3, n = 3
輸出：6
提示：
1 <= m, n <= 100- 題目資料保證答案小于等于
2 * 109
2.題目分析
這是一個二維的動態規劃，與一維動態規劃類似，二維狀態是由上一個狀態得來，如實體4:n=3,m=3
dp[0][0]=1,dp[0][1]=1;
dp[1][0]=1,dp[2][0]=1;
dp[0][2]=1;
dp[1][1]=dp[0][1]+dp[1][0]=2;
dp[1][2]=dp[0][2]+dp[1][1]=3;
dp[2][1]=dp[1][1]+dp[2][0]=3;
dp[2][2]=dp[2][1]+dp[1][2]=6;
從上述推導可以看出dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j];且要先計算i層才能計算i+1層，
3.代碼
class Solution {
public int uniquePaths(int m, int n) {
int dp[][]=new int[m][n];
dp[0][0]=1;
for(int i=1;i<m;i++)
dp[i][0]=1;
for(int i=1;i<n;i++)
dp[0][i]=1;
for(int i=1;i<m;i++)
for(int j=1;j<n;j++)
dp[i][j]=dp[i][j-1]+dp[i-1][j];
return dp[m-1][n-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/518518.html
標籤：其他