LeetCode – Refresh – Unique Paths II

 1 class Solution {
 2 public:
 3     int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
 4         if (obstacleGrid.size() == 0) return 0;
 5         int n = obstacleGrid.size(), m = obstacleGrid[0].size();
 6         vector<int> dp(n, 1);
 7         dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
 8         for (int i = 1; i < n; i++) {
 9             if (obstacleGrid[i][0] == 0) dp[i] = dp[i-1];
10             else dp[i] = 0;
11         }
12         for (int i = 1; i < m; i++) {
13             for (int j = 0; j < n; j++) {
14                 if (obstacleGrid[j][i] == 1) dp[j] = 0;
15                 else if (j == 0) continue;
16                 else {
17                     dp[j] += dp[j-1];
18                 }
19             }
20         }
21         return dp[n-1];
22     }
23 };