1
2
3
4
5
6

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

1
2

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设dp[m][n]: mxn网格的不同路径数;
    /// 2. 递推关系: dp[i][j] = 0 , obstacle_grid[i][j] == 1;
    ///                or    = dp[i-1][j] + dp[i][j-1], obstacle_grid[i][j] == 0;
    /// 3. 初始条件: dp[i][j] == 0,
    ///             dp[1][1] == 1,
    ///    注: 为统一处理边界情况,dp行列各增加一行,dp初始化分配[m+1][n+1]的空间;
    /// 4. 结果: dp[m][n]
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let (m, n) = (obstacle_grid.len(), obstacle_grid[0].len());
        let mut dp = vec![vec![0; n + 1]; m + 1];
        for i in 1..(m + 1) {
            for j in 1..(n + 1) {
                dp[i][j] = if obstacle_grid[i - 1][j - 1] == 1 {
                    0
                } else if i == 1 && j == 1 {
                    1 - obstacle_grid[0][0]
                } else {
                    dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }

        dp[m][n]
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
public:
    /*
    ## 解题思路
    * 动态规划
    1. f(m,n)代表到达m,n的方法数；
    2. f(m,n) = f(m-1,n) + f(m, n-1)
    3. 如果obstracleGrid[m][n]==1, 则f(m,n) = 0, 否则f(m,n) > 0;
    4. f(0,n),f(m,0)作为边界情况，需要单独处理；
    */
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> f(m, vector<int>(n, 0));
        for (int i=0; i <m; i++) {
            for(int j=0; j<n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                } else if (i == 0 || j==0) {
                    if (i==0 && j==0) {
                        f[i][j] = 1-obstacleGrid[i][j];
                    } else if (j>0) {
                        f[i][j] = f[i][j-1];
                    } else if(i>0) {
                        f[i][j] = f[i-1][j];
                    }
                } else {
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[m-1][n-1];
    }
    /*
    * 优化：
    5. 可以考虑扩展一行和一列，将第0行第0列变为第1行，第1列, 第0行第0列初始化为0，进行统一处理；
    6. 设置[0,1]为起始点,即f(0,1)=1;
    */
    int uniquePathsWithObstacles2(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> f(m+1, vector<int>(n+1, 0));
        f[0][1]=1; //从扩展的[0,1]格开始出发，[1,0]也可以，但不能同时
        for (int i=1; i <=m; i++) {
            for(int j=1; j<=n; j++) {
                if (obstacleGrid[i-1][j-1] == 0) { //obstacleGrid没有扩展
                    f[i][j] = f[i-1][j] + f[i][j-1];
                }
            }
        }

        return f[m][n];
    }
};