不同路径II

 1 class Solution {
 2 public:
 3     int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
 4         if(obstacleGrid.size() == 0) return 0;
 5         //define dp: dp[m][n]表示在位置[m][n]时到达右下角有dp[m][n]条路径
 6         int m = obstacleGrid.size();
 7         int n = obstacleGrid[0].size();
 8         if(obstacleGrid[m - 1][n - 1] == 1) return 0;
 9         vector<vector<long long>> dp(m, vector<long long>(n, 0));
10         //base case 
11         //这道题状态转移需要从最右下角开始，是确定状态base case
12         for(int i = m - 1; i >= 0; i--){
13             if(obstacleGrid[i][n - 1] == 1)
14                 break;
15             else
16                 dp[i][n - 1] = 1;
17         }
18         for(int j = n - 1; j >= 0; j--){
19             if(obstacleGrid[m - 1][j] == 1)
20                 break;
21             else
22                 dp[m - 1][j] = 1;
23         }
24         //for循环遍历所有状态
25         for(int i = m - 2; i >=0; i--){
26             for(int j = n - 2; j >= 0; j--){
27                 if(obstacleGrid[i][j] == 1)
28                     dp[i][j] = 0;
29                 else
30                     dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
31             }
32         }
33         return dp[0][0];
34 
35 
36     }
37 };