动态规划|【路径问题】63.不同路径II

题目

63. 不同路径 II

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

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

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

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

示例 1：

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

输出：2

解释：3x3 网格的正中间有一个障碍物。

从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

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

输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

题目解析

       跟上一篇博客62.不同路径有相似之处，机器人从strat位置走到finish位置，机器人只能向 下走或者向右走，现在多了一个条件就是这个m*n的网格中有障碍物，题目中说障碍物用1表示，然后求strat到达finish的 不同路径有多少。

       以上图为例，我们来分析，机器人刚开始再 【0，0】位置它可以向下或者向右走，我们先让机器人向下走达到【1，0】位置，【1，0】位置向右走是障碍物，向下走是空地，所以机器人，不能向右走，只能向下走到达【2，0】位置，【2，0】位置是边界，只能向右走到达【2，1】，【2，1】也是边界，只能向右走到达终点【2，2】

因此，这条路径是【0，0】-【1，0】-【2，0】-【2，1】-【2，2】

       当机器人第一步向右走，路径就是，【0，0】-【0，1】-【0，2】-【1，2】-【2，2】

动态规划思路

1.状态表示

首先还是得确定一个状态表示（以【i，j】位置为起点，或者以【i，j】为结尾）我们还是和上一篇一样，我们以【i，j】位置为结尾，我们要求起点到终点的路径方式

所以dp[i][j]表示起点到【i，j】位置的路径方式

2.状态转移方程

因为这道题相当于之前的题，多了一个障碍物，所以我们先分析障碍物

当【i，j】位置是障碍物的时候，从上面，或者从左边都是不能到这里的所以dp[i][j]=0

当【i，j】位置不是障碍物的时候，分析方法跟上一篇博客62.不同路径是一样的，所以状态转移方程就是dp[i][j]=dp[i-1][j]+dp[i][j-1]

注意，有些人可能会问当【i，j】旁边的位置是障碍物时，这个状态转移方程还能用吗？答案是肯定的

例如上面这个图，【i，j】位置不是障碍物，所以dp[i][j]=dp[i-1][j]+dp[i][j-1],【i，j-1】的位置是障碍物，所以从起点到【i，j-1】的路径就是0条，也就是dp[i][j-1]=0；所以加不加都不影响。

3.初始化

       初始化的目的就是为了填表的时候不越界，我还是采用虚拟结点（多开一行，多开一列）的方法，，方法跟上一篇博客62.不同路径 ，所以我们让原本的第一个格子的左边或者上边的值为1，其他全为0就行。

4.填表顺序

填表顺序当然也是，从上到下，从左到右

5.返回值

       题目问的是，从起点到终点的路径，加了虚拟结点后，终点的下标【m，n】了，所以返回dp[m][n]。

代码

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize)
{
    //创建dp表
    int dp[1000][1000]={0};
    //初始化
    dp[0][1]=1;
    int m=obstacleGridSize;
    int n=obstacleGridColSize[0];
    //填表
    for(int i=1;i<m+1;i++)
    {
        for(int j=1;j<n+1;j++)
        {
            //因为dp表多建了一行和一列，
            //例如每次会用地图中第一行，
            //第一列的值去填dp表中第二行第二列的值
            //第一行，第一列的值已经再初始化的时候填过了
           if(obstacleGrid[i-1][j-1]==1)dp[i][j]=0;
            else dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[m][n]; 
}

空间复杂度:O(mn)

时间复杂度:O(mn)