题解 | #不同路径的数目(二)#

动态规划问题，与没有障碍物的区别在于，初始化时第一行第一列遇到障碍物时，此处以及后面的dp都为0.且递推时，遇到障碍物dp为0，其他仍然按照dp[i][j]=dp[i-1][j]+dp[i][j-1]的递推关系进行。

function uniquePathsWithObstacles( obstacleGrid ) {
    // write code here
    const m = obstacleGrid.length,
          n = obstacleGrid[0].length;
    let dp = Array(m).fill().map(item => Array(n).fill(0));
    for(let i = 0; i < m; i ++){
        if(obstacleGrid[i][0]){
            dp[i][0] = 1;
        } else {
            break;
        }
    }
    for(let i = 0; i < n; i ++){
        if(obstacleGrid[0][i]){
            dp[0][i] = 1;
        } else {
            break;
        }
    }
    for(let i = 1; i < m; i ++){
        for(let j = 1; j < n; j ++){
            if(obstacleGrid[i][j]){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[m - 1][n - 1];
}
module.exports = {
    uniquePathsWithObstacles : uniquePathsWithObstacles
};