动态规划之路径问题

动态规划算法介绍

基本原理和解题步骤

针对于动态规划的题型，一般会借助一个 dp 表，然后确定这个表中应该填入什么内容，最终直接返回表中的某一个位置的元素。

细分可以分为以下几个步骤：

1. 创建 dp 表以及确定 dp 表中所要填写位置的含义：这一步关乎到最终推导出的状态转移方程，一般是根据题意或者根据以往做题的经验得出的。一般要么是以某一个位置结尾进行分析，要么是以某一个位置为开头进行分析。

2. 确定状态转移方程：是指针对 dp 表中的某一个单独分析，这个位置应该填入什么值。在进行这一步时，可以假设确定该位置元素时所需要的所有其他位置的值都已经确定了。

3. 初始化：有些题目，在创建完 dp 表之后，如果直接用状态转移方程填表，会导致越界的情况，所以要在某些会越界的位置单独进行初始化。

4. 确定填写 dp 表时的填写顺序：dp 表并不一定是从前往后填写的，因为有可能推导出的状态转移方程中，某一个位置中元素的值是跟该位置之后的位置有关的，所以填表顺序也应该结合题意和状态转移方程决定。

5. 确定返回值：根据题目要求找出应该返回 dp 表中的哪一个值。

例题

力扣 91. 解码方法

创建 dp 表以及确定 dp 表中所要填写位置的含义：

这道题中，根据解题经验，需要以某一个位置为结尾进行分析，即 dp[i] 表示在字符串 s 中，从开头到 i 位置这段子字符串中一共有多少种解码方法。

确定状态转移方程：

这道题的状态转移方程并不是一成不变的，需要分情况进行讨论。

所以，状态转移方程可以表示为 dp[i] = dp[i - 1] + dp[i - 2]，也就是上述两种情况的和。

 初始化：

由于推导出的状态转移方程中，dp[i] 的计算需要用到前两个位置的值，所以在开始填表之前，为了防止越界，需要先初始化确定 dp[0] 和 dp[1]。

dp[0]：第一个元素只能单独解码，解码成功为 1，解码失败为 0。

dp[1]：第二个元素可以单独解码，也可以和第一个元素一起解码，单独解码成功为 1，失败为0；单独解码不成功但是和前一个元素一起解码成功为 1，失败为0；单独解码成功，和前一个元素一起解码也成功为 2。

确定填表顺序：

由状态转移方程可以看出应该是从前向后填表。

确定返回值：

该题目需要返回以最后一个位置为结尾的字符串所有可能的解码总数，所以应该返回 dp[n - 1]。

代码：

class Solution 
{
public:int numDecodings(string s) {// 创建 dp 表int n = s.size();vector<int> dp(n);// 初始化if (s[0] == '0') return 0;dp[0] = 1;if (n == 1) return dp[0];if (s[1] != '0') dp[1] += 1;int t = (s[0] - '0') * 10 + (s[1] - '0');if (t >= 10 && t <= 26) dp[1] += 1;// 填表for (int i = 2; i < n; i++) {if (s[i] != '0') dp[i] += dp[i - 1];t = (s[i - 1] - '0') * 10 + (s[i] - '0');if (t >= 10 && t <= 26) dp[i] += dp[i - 2];}return dp[n - 1];}
};

但是，上面的初始化其实看起来有一些繁琐，可以通过增加虚拟节点的方式让代码变得更简洁。

说白了，就是在状态转移方程会越界的地方增加虚拟节点，并确保这个节点中的值不影响真正节点中填入的正确数据。

在这道题中，可以在 dp 的最前面增加一个位置，并初始化为 1，然后就只需要对字符串 s 的第一个字符进行判断，从第二个字符开始就可以使用状态转移方程了。

但是，注意，增加了一个虚拟节点之后，使用状态转移方程时要注意字符的下标是否和 dp 表的下标对应。

更改后的代码：

class Solution 
{
public:int numDecodings(string s) {// 创建 dp 表int n = s.size();vector<int> dp(n + 1);// 初始化dp[0] = 1;dp[1] = s[1 - 1] != '0';// 填表for (int i = 2; i <= n; i++) {if (s[i - 1] != '0') dp[i] += dp[i - 1];int tmp = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');if (tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];}return dp[n];}
};

动态规划中的路径问题

力扣 62. 不同路径

力扣 62. 不同路径

这道题中的路径可以模拟为一个 m 行 n 列的二维数组。

解题步骤：

创建 dp 表以及确定 dp 表中所要填写位置的含义：

首先，根据写题经验，先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。

其次，由于要记录路径中的每一个位置，所以这道题的 dp 表应该是一个m 行 n 列的二维数组。

每一个位置的含义，也就是 dp[i][j] 指的是，从（0， 0）到 （i，j）位置一共有多少种路径。

确定状态转移方程：

题目指出，每一次移动只能向下或者向右移动，所以到达（i，j）位置之前的一个位置一定是（i - 1，j）或者（i，j - 1）。

所以，（i，j）位置的路径总数应该是（i - 1，j）和（i，j - 1）两个位置路径总数之和。

所以，dp[i][j] = dp[i - 1][j] + dp[i][j -1]。

初始化：

由于第一行和第一列中的元素，只能由自己的前一个位置到达，所以它们所对应的 dp 表中的值应该是 1。

确定填表顺序：

根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。

确定返回值：

题目要求返回到达（m，n）的所有路径总数，所以应该返回 dp[m - 1][n - 1]。

代码：

class Solution 
{
public:int uniquePaths(int m, int n) {// 创建 dp 表vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 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 - 1][n - 1];}
};

力扣 63. 不同路径（二）

力扣 63. 不同路径（二）

这道题跟上面的题唯一的不同在于，需要注意二维数组中存在障碍物的位置。

原理还是一样的，只是，如果某一个位置的上边或者左边有障碍物，就不应该再加上这条路径。

其他过程不再赘述。

代码：

class Solution 
{
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if (obstacleGrid[0][0] == 1) return 0;int m = obstacleGrid.size(), n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1) return 0;// 创建 dp 表vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化for (int i = 0; i < m; i++){if (obstacleGrid[i][0] == 0) dp[i][0] = 1;else break;} for (int j = 0; j < n; j++){if (obstacleGrid[0][j] == 0) dp[0][j] = 1;else break;}// 填表for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){// 如果有障碍物, 就不做处理, 保持 0 值if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

力扣 166. 珠宝的最高价值

力扣 166. 珠宝的最高价值

解题步骤：

创建 dp 表以及确定 dp 表中所要填写位置的含义：

首先，根据写题经验，先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。

其次，由于要记录路径中的每一个位置，所以这道题的 dp 表应该是一个m 行 n 列的二维数组。

每一个位置的含义，也就是 dp[i][j] 指的是，从（0， 0）到 （i，j）可以拿到的珠宝的最高价值之和。

确定状态转移方程：

题目指出，每一次移动只能向下或者向右移动，所以到达（i，j）位置之前的一个位置一定是（i - 1，j）或者（i，j - 1）。

所以，（i，j）位置的最大价值应该是（i - 1，j）和（i，j - 1）两个位置中的最大价值和（i，j）位置本身的价值之和。

所以，dp[i][j] = max(dp[i - 1][j] + dp[i][j -1]) + frame[i][j]。

初始化：

由于第一行和第一列中的元素，只能由自己的前一个位置到达，所以它们所对应的 dp 表中的值应该是本身的价值加上前一个位置的最大价值。

确定填表顺序：

根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。

确定返回值：

题目要求返回到达右下角时能拿到的珠宝的最大价值，所以应该返回 dp[m - 1][n - 1]。

代码：

class Solution 
{
public:int jewelleryValue(vector<vector<int>>& frame) {// 创建 dp 表int m = frame.size(), n = frame[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));// 初始化dp[0][0] = frame[0][0];for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + frame[i][0];for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + frame[0][j];// 填表for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];}}return dp[m - 1][n - 1];}
};

力扣 931. 下降路径最小和

力扣 931. 下降路径最小和

解题步骤：

创建 dp 表以及确定 dp 表中所要填写位置的含义：

首先，根据写题经验，先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。

其次，这道题目的 “结尾” 指的是最后一行，而不是右下角。

dp[i][j] 指的是 从第一行到（i，j）位置路径上所有点相加的最小值。

确定状态转移方程：

由题目可得，到达（i，j）位置之前的一个位置一定是（i - 1，j）或者（i - 1，j - 1）或者（i - 1，j + 1）。

所以，（i，j）位置的最小路径和应该是（i - 1，j）（i - 1，j - 1）以及（i - 1，j + 1）三个位置中的最小值和（i，j）位置本身的值相加

所以，dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j -1], dp[i - 1][j + 1])) + matrix[i][j]。

初始化：

这道题可以直接用 matrix 二维数组来初始化 dp 表，后续可以直接在此基础上更改。

确定填表顺序：

根据状态转移方程可以看出应该从上往下每一行依次填入数据。

确定返回值：

题目要求返回到达最后一行的路径上和的最小值，所以应该返回 dp 表中最后一行中的最小值。

代码：

class Solution 
{
public:int minFallingPathSum(vector<vector<int>>& matrix) {// 创建 dp 表 + 初始化vector<vector<int>> dp(matrix);// 填表int n = matrix.size();for (int i = 1; i < n; i++){for (int j = 0; j < n; j++){if (j == 0)dp[i][j] += min(dp[i - 1][0], dp[i - 1][1]);else if (j == n-1)dp[i][j] += min(dp[i - 1][n - 1], dp[i - 1][n - 2]);else{int Min = min(dp[i - 1][j - 1], dp[i - 1][j]);dp[i][j] += min(Min, dp[i - 1][j + 1]);}}}int min = dp[n - 1][0];for (int i = 1; i < n; i++)min = dp[n - 1][i] < min ? dp[n - 1][i] : min;return min;}
};

力扣 64. 最小路径和

力扣 64. 最小路径和

解题步骤：

创建 dp 表以及确定 dp 表中所要填写位置的含义：

首先，根据写题经验，先确定出这道题应该使用的解题思路是 “以某一个位置为结尾进行分析”。

其次，由于要记录路径中的每一个位置，所以这道题的 dp 表应该是一个m 行 n 列的二维数组。

每一个位置的含义，也就是 dp[i][j] 指的是，从（0， 0）到 （i，j）所有路径中的最小和。

确定状态转移方程：

题目指出，每一次移动只能向下或者向右移动，所以到达（i，j）位置之前的一个位置一定是（i - 1，j）或者（i，j - 1）。

所以，（i，j）位置的最小路径和应该是（i - 1，j）和（i，j - 1）两个位置中的最小值和（i，j）位置本身的值之和。

所以，dp[i][j] = min(dp[i - 1][j] , dp[i][j -1]) + grid[i][j]。

初始化：

这道题可以按照先开一个二维数组，再初始化第一行和第一列的方法初始化。

但是，也可以直接用题目给出的原数组初始化，虽然后续还是要对第一行和第一列进行改动。

各位看自己心情选择吧。

确定填表顺序：

根据状态转移方程可以看出应该从二维数组的左上角到右下角依次填入数据。

确定返回值：

题目要求返回到达右下角的所有路径和中的最小值，所以应该返回 dp[m - 1][n - 1]。

代码：

class Solution 
{
public:int minPathSum(vector<vector<int>>& grid) {// 创建 dp 表int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(grid);// 初始化for (int i = 1; i < m; i++) dp[i][0] += dp[i - 1][0];for (int j = 1; j < n; j++) dp[0][j] += dp[0][j - 1];// 填表for (int i = 1; i < m; i++){for (int j = 1; j < n; j++){dp[i][j] += min(dp[i - 1][j], dp[i][j - 1]);}}return dp[m - 1][n - 1];}
};

力扣 174. 地下城游戏

力扣 174. 地下城游戏

这道题就有点不一样了，它不能用 “以某一个位置为结尾进行分析”。

解题步骤：

创建 dp 表以及确定 dp 表中所要填写位置的含义：

如果还是以某一个位置为结尾进行分析，则 dp[i][j] 表示从七点到达（i，j）位置所需的最低健康点数，这时虽然知道了 dp[i -1][j] 和 dp[i][j - 1]，但是就算可以保证骑士可以到达（i，j），但是能不能到达最后还受后面数字的影响，所以这个方法行不通。

如果以某一个位置为起点进行分析，则 dp[i][j] 表示骑士从（i，j）位置到最后所需的最低健康点数，这时可以从右下角开始。

确定状态转移方程：

dp[i][j] 表示从 i, j 位置出发到达终点所需的最小的健康点数

往右边走：则该位置的健康点数减去该位置消耗的健康点数应该大于等于右边位置所需的健康点数

dp[i][j] + dungeon[i][j] >= dp[i][j + 1] -> dp[i][j] >= dp[i][j + 1] - dungeon[i][j]

往下边走：则该位置的健康点数减去该位置消耗的健康点数应该大于等于下边位置所需的健康点数

dp[i][j] + dungeon[i][j] >= dp[i + 1][j] -> dp[i][j] >= dp[i + 1][j] - dungeon[i][j]

所以，dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

初始化：

这道题我用的方法是，先开一个二维数组，然后初始化最后一行和最后一列。

当然如果你有更喜欢的方法也可以。

各位看自己心情选择吧。

确定填表顺序：

根据状态转移方程可以看出应该从二维数组的右下角到左上角依次填入数据。

确定返回值：

题目要求求出从起点能顺利到达右下角所需的最低健康点数，所以应该返回 dp[0][0]。

还有一个需要注意的点：由状态转移方程可以看出一个漏洞，如果dungeon[i][j]的值是一个很大的正数则会导致dp[i][j] < 0表明骑士已经死亡， 所以当dp[i][j]为负数时，应将其变为1 dp[i][j] = max(1, dp[i][j])。

代码：

class Solution 
{
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {// 创建 dp 表int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m, vector<int>(n));// 初始化dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1];dp[m - 1][n - 1] = max(1, dp[m - 1][n - 1]);for (int i = m - 2; i >= 0; i--){dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i][n - 1];dp[i][n - 1] = max(1, dp[i][n - 1]);}for (int j = n - 2; j >= 0; j--){dp[m - 1][j] = dp[m - 1][j + 1] - dungeon[m - 1][j];dp[m - 1][j] = max(1, dp[m - 1][j]);}// 填表for (int i = m - 2; i >= 0; i--){for (int j = n - 2; j >= 0; j--){dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]);}}return dp[0][0];}
};

总结

在我看来，动规问题中的路径问题应该有以下几点值得注意的：

1. 开出来的 dp 表中，每一个位置到底代表什么。

2. 填表的时候一定要注意在容易越界的地方，进行合适的初始化，初始化的数据一定不能影响后面数据的正确性。

3. 到底该 “以某一个位置为结尾” 还是 “以某一个位置为起点” 应该看 dp 表中的某一个位置的值，是否还受后面的值的影响。