62.不同路徑

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

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

問總共有多少條不同的路徑？

1. 定義dp[i][j]：到ij這個位置有幾種方法

2. 狀態轉移方程：dp[i][j] = dp[i-1][j]+dp[i][j-1]

3. 初始化：如何初始化呢，首先dp[i][0]一定都是1，因為從(0, 0)的位置到(i, 0)的路徑只有一條，那么dp[0][j]也同理。

????????dp[i][0] = 1; dp[0][i] = 1;

4. 遍歷順序：從左上角到右下角

5. 舉例打印。

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n,0));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];}
};

• 時間復雜度：O(m × n)
• 空間復雜度：O(m × n)

63. 不同路徑 II

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

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

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

1.?dp[i][j] ：表示從（0 ，0）出發，到(i, j) 有dp[i][j]條不同的路徑。

2. dp[i][j] = dp[i-1][j]+dp[i][j-1]. if obs[i][j]==0

3.初始化：obs[i][0]==0/obs[0][j]==0, dp[i][0]=1, dp[0][j]=1;

4. 遍歷，從左上角到右下角，碰到obstacles直接continue。

5. 舉例打印。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));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];}
};

• 時間復雜度：O(n × m)，n、m 分別為obstacleGrid 長度和寬度
• 空間復雜度：O(n × m)