本文主要是介绍leetcode63.跳跃游戏2（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例一：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右 对应的图片：
示例二：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1对应的图片：
问题解决：
这道题与跳跃游戏那道题基本一样，只是多了障碍物。
1.状态表示
因为本题是二维表格的最短路径，所以dp数组也要是二维的：
dp[i][j]表示走到 [i,j] 的时候一共有多少种不同的路径
2.状态转移方程
要想求到达dp[i][j]一共有多少条路径，题干规定机器人每次只能向下或者向右移动一步，首先得判
断对应的节点是不是有障碍，如果有，直接返回0，没有就必须知道到达dp[i - 1][j]有多少条路径，
还有到达dp[i][j - 1]有多少条路径，这两条路径不是二选一，而是全都满足条件，所以应该全部加到
dp[i][j]中。
对应dp[i][j]的状态转移方程：
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
3.初识化一些值：
这道题要直接进行初始化，初始化的值很多，需要将第一行和第一列的之全部初始化，不然就会有
位置找不到有多少条路径，这是就要与上次解码方法类似添加一行一列辅助节点，同样是两个问
题：
1.如何填写虚拟节点里面的值，使之后的填表顺序进行？
其实在添加了一行一列辅助虚拟节点之后，最需要虚拟节点的是原来的第一行和第一列的dp数组表
那么元dp数组的左上角应该填的是什么，从起点出发到达起点只有一种方法，所以应该填写1，但
是要通过这些虚拟头节点来实现左上角的值为1，而且也满足其他要初始化的节点，所以可以在添
加了虚拟数组之后，在第一行第二列将其赋值为1，也可以将第二行第一列的节点赋值为1，
这样就只用初始化一个节点了。
2.关于添加了虚拟节点的数组和dp数组的映射关系
因为这道题传的是二维数组，所以在访问其元素时一定要记得将dp对应的位置的下标 - 1 之后在进
行访问，这才是我们想要访问的所传的数组中的元素。
4.填表顺序
每一行从上到下
行里每一列从左到右
5.返回值
dp[m][n],应为添加了虚拟节点，数组也变大了，所以要求的结果是对应dp[m][n]，其中m是行数
n是列数。
对应代码：
class Solution
{
public:int uniquePathsWithObstacles(vector<vector<int>>& ob) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = ob.size(), n = ob[0].size();vector<vector<int>> dp(m + 1,vector<int>(n + 1));dp[1][0] = 1;for(int i = 1;i <= m;i++) {for(int j = 1;j <= n;j++){if(ob[i - 1][j - 1] == 0){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m][n];}
};这就是这道题的解法，只需增加判断有没有障碍即可。
这篇关于leetcode63.跳跃游戏2（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
