目录
题目
题目解析
动态规划思路
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
代码
题目
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.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[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)
