解锁动态规划的奥秘：从零到精通的创新思维解析（3）

前言：

小编在前几日书写了关于动态规划习题的博客（PS：其实这些都是我的存稿，我已经好久没写博客了截止到现在，确实摆烂），今天各位继续跟着小编的步伐，走进动态规划的世界，接下来我们将会·讲述一个比较新的动态规划问题：路径问题。

正文：

1.不同路径

1.1.题目来源

本题和之前的题目一样，都是来自于力扣，下面小编给上链接：62. 不同路径 - 力扣（LeetCode）

1.2.题目解析

和之前的规矩一样，小编先给各位分析一下题目到底想要传达给我们什么信息，其实本题也是很好理解的，这个题目就像我们小学做过的益智游戏一样，此时给定我们一个机器人，此时我们从左上角开始走，想要我们求解走到右下角的方法有几种，此时我们选择往右走，也可以选择往下走，只要走到右下角即可。这就是一个典型的路径问题，通过动态规划我们就可以轻易解决此类问题，下面小编进入本题的思路讲解部分。

1.3.思路讲解

对于动态规划的题目，我们首先需要先设置好一个dp表用于存放数据，此时根据题目分析我们可以知道此时我们需要设置一个二维的dp表，因为我们可以通过行走，也可以通过列走。设置完表后，此时我们就要五步走来解决动态规划的题目了。

1.状态表示

此时我们需要弄清楚此时的dp表是什么，对于线性的dp表示，我们通常可以是经验+题目要求来解决，所以此时我们通过题目分析可以得出dp[i] [j]此时表示到达[I，j]位置时的方法（路径），下面我们依据这个dp表可以构建一个状态转换方程。

2.状态转换方程

此时我们对于状态转移方程的分析，同样也是需要借助题目来进行表示，此时我们可以知道到达[i，j]位置时的方法有两种，分别是从上面或者从左边到达，所以此时我们达到[i，j]位置时的路径，可以表示为两个方法之和，那么此时我们就可以得到方程了：

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  //分别是从左，从上

3.初始化

此时我们写完方程后就要注意细节问题了，此时的初始化问题也很明显，此时如果i或者j为0的话，那么上面和左边就会越界，所以第一个解决方法就是我们把第一排和第一列给全部初始化，但是这样无疑是增加工作量，并且出错的概率会加大，所以小编不推荐这个方法，小编认为本题目最好的求解方法就是：增加虚拟节点的方法来解决初始化问题，简单来说就说我们在创建dp表的时候，多开辟一行一列，此时我们仅需从第二排和第二列初始化即可，这样就避免了越界问题，不过对于增加虚拟节点，我们需要有两个注意事项：

1. 虚拟节点不会影响后面填表的正确性。
2. 我们填表的时候需要注意下标的映射（代码会体现）

此时对于1，我们对于虚拟节点的初始化，此时还是蛮好填的，我们只要让第一个节点的上或者左为1即可，因为第一个节点也表示着一条路径，其他位置填零即可，此时我们就做到了填表的正确性。

对于2，此时我们只要记住dp表是多开辟一行一列的，所以我们在使用nums（本题没有）的时候行列减1即可，当然，本题目没有用到它，但是小编后面讲述的其他题需要注意这个点。

4.填表顺序

因为此时我们需要用到前面的元素，所以我们从上到下，从左到右填写即可。

5.返回值

因为本题目是想要达到最后一个位置的方法，所以我们返回dp[m] [n]即可。

以上便是思路讲解，下面我们进入代码讲解。

1.4.代码讲解

此时我们需要先设置好一个dp表，那么我们就需要计算此时给定我们表格的行列，之后多开辟一行一列即可，并且让第一个位置的上面为1即可。

vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));
dp[0][1] = 1;

之后我们就要进入循环，循环的开头是第二行第二列，结尾是第m行，第n列，此时循环里面的内容自然是状态转移方程，填完dp表以后，我们返回表中最后一个元素所代表的方法即可。

for(int i = 1 ; i <= m ;i++){for(int j = 1 ; j <= n ; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}   }
return dp[m][n];

1.5.代码展现

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));dp[0][1] = 1;for(int i = 1 ; i <= m ;i++){for(int j = 1 ; j <= n ; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}   }return dp[m][n];}
};

2.不同的路径Ⅱ

2.1.题目来源

本题同样来自于力扣，下面小编给上链接：63. 不同路径 II - 力扣（LeetCode）

2.2.题目解析

本题目其实就是上题的pro版，仅仅就是比上面那题多了一个障碍物，此时无非就是遇到障碍物我们就走不了而已，其他和上一个题目一样，所以我就不用详细讲述本题目所代表的意思了，直接进入本题的思路部分。

2.3.思路讲解

此时的dp的设置也是和上个题目一样，我们需要设置好一个二维的dp表，因为我们可以选择从行走，也可以选择从列走，之后我们依旧是按照五步走来完成本题目的分析。

1.状态表示

此时我们的状态表示其实和上个题目是一样的，他们的差距仅仅体现在状态转移方程，所以一些话我就直接复制了，此时我们需要弄清楚此时的dp表是什么，对于线性的dp表示，我们通常可以是经验+题目要求来解决，所以此时我们通过题目分析可以得出dp[i] [j]此时表示到达[I，j]位置时的方法（路径），下面我们依据这个dp表可以构建一个状态转换方程。

2.状态转换方程

此时这里才是两个题目的不同之处，因为本题目增加了障碍物，所以此时我们并不可以直接无脑的从上面到达目的地，从左边达到目的地了，我们到达一个位置的时候需要判断此时这个位置是否有障碍，如果有障碍的话，那么我们之前的路白走了，此时的dp表填0，如果没有障碍物，我们还是和上个题目一样分两种情况到达该位置，上图就很好的表示出了此时的方程分析。

3.初始化

此时我们的初始化也是和上面题目一样，我们通过增加一行一列的虚拟节点来表示此时的dp表，此时我们原来的第一个位置也算一个路径，所以此时我们让它的上边或者左边为1即可，和上个题目一摸一样，只不过此时我们需要注意下标的映射，因为此时我们多建了一行一列，所以此时我们在填表的时候，原数组行列均减一。

4.填表顺序

从上到下，从左到右。

5.返回值

此时我们返回最后一个位置所对应的dp表里面的值即可。

2.4.代码讲解

此时，我们依旧是设置好一个dp表，并且按照上面说的对特定元素进行初始化。

int m = obstacleGrid.size(),n = obstacleGrid[0].size();  //m表示行，n表示列
vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));//多开辟一个放置虚拟结点
dp[0][1] = 1;

之后我们还是循环进行填表，当然，我们在填表的时候应该注意此时数组对应位置的元素是否为0，如果是0的话我们就依旧和上面那个题目一样进行填表，如果是1的话，那么我们也无需设置其为0，因为此时的dp表里面除了特定位置，其余位置均为0（STL中vector的性质）。填完表后，我们返回dp表最后一个位置的元素即可。

for(int i = 1 ; i <= m ; i++){for(int j = 1 ; j <= n ;j++){if(obstacleGrid[i - 1][j - 1] == 0)dp[i][j] = dp[i-1][j] + dp[i][j - 1];}}
return dp[m][n];

2.5.代码展示

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size(),n = obstacleGrid[0].size();  //m表示行，n表示列vector<vector<int>> dp(m + 1,vector<int>(n + 1,0));//多开辟一个放置虚拟结点dp[0][1] = 1;for(int i = 1 ; i <= m ; i++){for(int j = 1 ; j <= n ;j++){if(obstacleGrid[i - 1][j - 1] == 0)dp[i][j] = dp[i-1][j] + dp[i][j - 1];}}return dp[m][n];}
};

3.总结

此时本文到这也就结束了，今天小编讲述的两个题目关联性很强，所以小编推荐各位可以做完第一个题目的时候，先不看我的分析，直接上手第二个题目就可以，因为第二个题也就在方程那部分和第一题有些许的不同，其他的分析方法和第一个题目都是一样的，如果文章有错误的话，请在评论区指出，小编会定时看评论区对本文进行更正，一起刷题的时光总是短暂的，那么各位大佬们，我们下一篇文章见啦！