63.md

63. Unique Paths II

Leetcode link

解题思路

本题要求我们在一个 m * n 的矩阵中，计算从左上角走到右下角不碰到障碍物的所有路径

本题解法有两种思路：dfs 以及动态规划

首先来看一下 dfs，dfs 的方法会要求我们遍历所有可能的路径，我们来看一下它的时间复杂度：

因为每一个节点有两种可能的走法：向下跟向右，而所有的节点总共有 m * n 个，所以总共要做 m * n 次抉择

因此时间复杂度为 O(2 ^ (m * n))

接下来，我们来看看动态规划

首先，我们用一个二维数组 dp，其中 dp[i][j] 表示矩阵中下标为 (i, j) 的位置能够到达的路径数量

根据题目中只能向下走跟向右走的限制，我们可以轻易得出如下等式：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

如果没有障碍物的话，到这里已经结束了，但是题目的另一个约束条件就是路径上可能有障碍物，所以，我们格局需要再打开一点

具体而言，我们可以把目前 m * n 的 dp 数组分别在左边跟上面加上一列以及一行，使其大小为 (m + 1) * (n + 1)

然后我们可以把 dp 数组初始化为 0，然后在 (1, 0) 或者 (0, 1) 的位置初始化为 1 就好了

详情看代码

C++

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size(),
        n = obstacleGrid[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        dp[0][1] = 1;
        
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if(obstacleGrid[i-1][j-1] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

Javascript

var uniquePathsWithObstacles = function(obstacleGrid) {
    let m = obstacleGrid.length, n = obstacleGrid[0].length;
    // dp[m+1][n+1]
    let dp = new Array(m+1);
    for(let i=0;i<=m;i++) {
        dp[i] = new Array(n+1).fill(0);
    }
    dp[1][0] = 1;
    
    for(let i=1;i<=m;i++) {
        for(let j=1;j<=n;j++) {
            if(obstacleGrid[i-1][j-1] === 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[m][n];
};