62.不同路徑

一個機器人位于一個 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

本題會想到是一個深度搜索的問題，用二叉樹求解，但是這樣會超出時間限制，這種下一步需要上一步來推導的，可以優先考慮動態規劃。因為本題要求有多少條從起點到終點的可能路徑，這里需要定義的是一個二維數組，因為坐標包括兩個值，start為[0,0]，end為[m-1, n-1]。dp為路徑條數。。題目規定每次只能向右或向下移動。所以到終點end的時候，上一步只能是來自其左邊或者上邊，所以end的位置只能來自(m-2, n-1)或(m-1, n-2)。

1. 確定dp數組以及下標的含義：dp[i][j]表示從(0,0)出發，到(i, j) 有dp[i][j]條不同的路徑。
2. 確定遞推公式：因為終點只能通過其左或者上面到達，所以dp[i][j]=dp[i-1][j]+dp[i][j-1]
3. dp數組如何初始化：因為只能從上或左走，不存在斜著走的情況，所以從(0,0)到達(0,n)或(m,0)只能一直向下或向左，可能路徑條數均為1，即dp[i][0]=1，dp[0][j]=1
4. 確定遍歷順序：遍歷順序就是從1開始左向右，從上到下一層層遍歷
5. 舉例推導dp數組：這里沒法直接給出dp的舉例

class Solution {public int uniquePaths(int m, int n) {int[][] dp=new int[m][n];for(int i=0;i<m;i++) dp[i][0]=1;for(int j=0;j<n;j++) dp[0][j]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}

63. 不同路徑 II

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中標記為“Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為“Finish”）。

現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

本意跟上一題不用路徑的區別在于，這里多了障礙物的限制條件，因此當存在障礙物的時候，這條路徑就被去掉即可，因此初始化和遍歷時，都需要多加一個判斷障礙物的條件，如果(i,j)位置有障礙物，就為0。如果起點和終點有障礙物，則為0。

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//先定義m和nint m=obstacleGrid.length;int n=obstacleGrid[0].length;int[][] dp= new int[m][n];if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) return 0;for(int i=0;i<m && obstacleGrid[i][0]==0;i++) dp[i][0]=1;for(int j=0;j<n && obstacleGrid[0][j]==0;j++) dp[0][j]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==1) continue;dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}