方法一：动态规划

最近做了很多动态规划的题目，看到类似求：“一共多少xxx” 的问题就想到动态规划。

想到动态规划，那么就需要把动态转移方程找到；

我们观察题目，因为每次只能向下或者向右移动一步，所以我们从后向前思考。如果到达右下角的位置，那么能够有哪几种可能？

• 从左上方到达
• 从右边一格到达

我们需要构建一格二维数组，存放到达每一个位置的路径数。那么如果用 dp[i][j] 表示能到达第 i 行 第 j 列元素的路径数，那么：

• 如果当前格子没有障碍 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
• 如果当前格子有障碍： dp[i][j] = 0

用题目中所给的🌰得出 dp 数组（图中橙色部分）如下图所示

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int row = obstacleGrid.size();
        int column = obstacleGrid.at(0).size();
        vector<vector<int>> dp(row + 1, vector<int>(column + 1, 0));
        for(int i = 1; i < row + 1; i++){
            for(int j = 1; j < column + 1; j++){
                if(obstacleGrid[i - 1 ][j - 1] == 1){
                    // 有障碍
                    dp[i][j] = 0;
                }else{
                    // 没有障碍
                    // 初始化
                    if(i == 1 && j == 1){
                        dp[1][1] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
        }
        return dp[row][column];
    }
};