[数据结构与算法]【Leetcode】63. 不同路径 II

题目链接：不同路径II

题目描述：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

分析：

这个题目本来是用回溯写的，但是超时了。无奈之下，看了一眼题解，原来是DP!!!

dp[i][j]表示从起点(0,0)到点(i,j)的路径数。因为机器人只能向下或向右移动，所以当机器人在某个点时，只能来自于该点上方或左侧的两个点，即到达该点的路径数=到达其上方的路径数+到达其左侧的路径数。

那么显然，状态转移方程：

1)当obstacleGrid[i][j]==1时，即障碍物，则dp[i][j]=0。

2)当obstacleGrid[i][j]==0时，dp[i][j]=dp[i-1][i]+dp[i][j-1]

边界条件：当obstacleGrid[0][0]==1时，dp[0][0]=0；否则dp[0][0]=1。

又因为，dp[i][j]只和其上方和左侧的数据有关，所以dp可以是一个一维数组。

js代码如下：

// 动态规划
 var uniquePathsWithObstacles = function(obstacleGrid) {
    let m=obstacleGrid.length;
    let n=obstacleGrid[0].length;
    if(m==1 && n==1){
        return obstacleGrid[0][0]==0?1:0;
    }
    const dp=new Array(n).fill(0);
    dp[0]=obstacleGrid[0][0]==0?1:0;
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(i==0 && j==0)
                continue;
            else if(i==0){
                dp[j]=obstacleGrid[i][j]==0?dp[j-1]:0;
            }
            else{
                if(obstacleGrid[i][j]==0){
                    if(j==0)
                        continue;
                    else
                        dp[j]=dp[j-1]+dp[j];
                }
                else
                    dp[j]=0;
            }   
        }
    }
    return dp[n-1];
    
};

时间复杂度O(mn)，空间复杂度O(n)。