【动态规划】--- 路径问题

Welcome to 9ilk's Code World

(๑•́ ₃ •̀๑) 个人主页: 9ilk

(๑•́ ₃ •̀๑) 文章专栏：算法Journey

🏠 不同路径

📌 题目解析

62. 不同路径 - 力扣（LeetCode）

📌 算法原理

解法一

（1）状态表示：

dp[i][j]表示走到[i,j]位置，一共有多少种方式。

（2）状态转移方程：

我们从最近的一步分析问题，由于机器人每次只能向下或向右走，因此走【i,j】位置，只能从【i-1，j】或【i,j-1】位置过去，此时问题转化为走到(i-1,j)或(i，j-1)位置一共有多少种方式，这刚好就是我们的状态表示，由于求的是一共多少种，只需进行相加即可，即：dp[i][j] = dp[i-1][j] + dp[i][j-1]

（3）初始化

由于状态转移方程使用了上一行和上一列的状态，此时对于0下标可能导致越界，我们可以采用虚拟节点的方法来使状态转移的合法性，但需要注意两个问题：

虚拟节点里面的值，要保证后面填表的结果是正确的
下标的正确映射。（访问原数组元素时下标-1）

（4）填表顺序

由状态转移方程得，我们的状态填写依赖上一行和上一列的状态，因此我们填表顺序是从上往下填写，每一行从左往右填写。

（5）返回值

我们的状态表示为走到某位置一共有多少种方式，由题目要求得，我们需要求的是到达右下角，即dp[m][n]，注意由于添加了虚拟节点，所以我们需要在原来下标基础上加1

参考代码：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));//初始化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];   }
};

解法二

(1) 状态表示

dp[i][j] 表示从(i,j)位置到达终点一共有多少种方式

(2) 状态转移方程

同样的，我们从最近一步位置分析：当我们走到（i，j）位置此时只能往下走或向右走，此时问题转化为从(i+1,j)或(i,j+1)位置到达终点一共有多少种方式。

即：dp[i][j] = dp[i+1][j] + dp[i][j+1]

(3) 初始化

我们同样采用虚拟节点，也要注意两个问题：

（4）填表顺序

由状态转移方程得，我们的状态填写依赖下一行和下一列的状态，因此我们填表顺序是从下往上填写，每一行从右往左填写。

(5) 返回值

我们状态表示为从(i,j)位置出发到达右下角一共有多少方式,我们题目要求的是从(0,0)到右下角,此时应该返回(0,0)

参考代码:

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

🏠 不同路径II

📌 题目解析

63. 不同路径 II - 力扣（LeetCode）

📌 算法原理

(1) 状态表示

dp[i][j]表示到达(i,j)位置的时候,一共有多少种方法

(2) 状态转移方程

从最近一步分析,由于机器人只能享下或向右移动,所以我们只能从(i-1,j)或(i,j-1)位置移动到(i,j)

1. 如果(i,j)位置本身有障碍物,是没有方法能到达该位置的,此时dp[i][j] = 0。

2. 如果(i,j)位置本身没障碍物，要么从左边来，要么从上边来，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。

(3) 初始化

初始化我们添加虚拟节点，仍然需要注意两个问题：

1. 保证后面填表是正确的。

2. 下标的映射关系。

（4）填表顺序

由状态转移方程得，我们的状态填写依赖上一行和上一列的状态，因此我们填表顺序是从上往下填写，每一行从左往右填写。

（5）返回值

我们的状态表示为走到某位置一共有多少种方式，由题目要求得，我们需要求的是dp[m][n]

参考代码：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));dp[0][1] = 1;for(int i = 1 ; i <= m ; i++)for(int j = 1 ; j<= n ; j++){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];    }
};

🏠 礼物的最大价值

📌 题目解析

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

📌 算法原理

（1）状态表示

dp[i][j]：到达(i，j)位置时，此时的最大价值。

（2）状态转移方程

由题目知，每次移动时，只能向右或向下移动，因此到达(i,j)位置，我们需要先知道到达它左边或上方位置时所需要的最大价值(就是我们的状态表示)，选其中最大的再加上自身位置珠宝的价值。

dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + g[i][j] ；

（3）初始化

我们填充虚拟节点只需都初始化为0即可。

（4）填表顺序

由状态转移方程得，我们的状态填写依赖上一行和上一列的状态，因此我们填表顺序是从上往下填写，每一行从左往右填写。

（5）返回值

我们的状态表示为走到某位置一共有多少种方式，由题目要求得，我们需要求的是到达右下角，即dp[m][n]

参考代码：

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

🏠 下降路径最小和

📌 题目解析

931. 下降路径最小和 - 力扣（LeetCode）

📌 算法原理

（1）状态表示

dp[i][j]表示到达(i，j)位置时的最小下降路径和。

（2）状态转移方程

由本题得知，要想到达(i,j)位置，可以从3个方向到达，即左上角，正上方，右上角，此时我们需要选出它们当中下降路径和最小的，再加上该位置本身的元素即可。

dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + martix[i-1][j-1]

（3）初始化

我们采用虚拟节点，注意本题需要访问原数组的元素，这意味着我们使用虚拟节点之后，访问原数组元素需要下标在原来基础上-1:

(4) 填表顺序

由状态转移得知,我们依赖的状态都是上一行的状态,所以我们填表时只需要确保从上往下即可

(5) 返回值

由题目可知,当到达最后一行时,路径遍历结束,因此要求最小下降路径和,我们只需返回dp表中最后一行的最小值即可。

参考代码：

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix){int m = matrix.size();int n = matrix[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 2, 101*n));//第一行填0for (int i = 0; i < n + 2; i++){dp[0][i] = 0;}for (int i = 1; i <= m; i++){for (int j = 1; j <= n; j++){int Min = 0;//dp[i-1][j-1] dp[i-1][j] dp[i-1][j+1]Min = dp[i - 1][j - 1];for (int n = j - 1; n <= j + 1; n++){Min = min(Min, dp[i-1][n]);}dp[i][j] = Min + matrix[i - 1][j - 1];}}//看最后一行int Min = dp[m][1];for (int j = 2; j <= n; j++){Min = min(Min, dp[m][j]);}return Min;}
};

🏠 最小路径和

📌 题目解析

64. 最小路径和 - 力扣（LeetCode）

📌 算法原理

（1）状态表示

dp[i][j] : 到达(i,j)位置时，所能获得的最小路径和

（2）状态转移方程

同样的我们从最近一步划分问题，我们每次移动只能向下或向右移动，因此到达(i，j)位置只能从左边或上方来，所以我们需要知道到达(i-1,j)和(i,j-1)位置的最小路径和，再加上自身位置的元素。

dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + g[i][j]

(3) 初始化

（4）填表顺序

由状态转移方程得知，我们依赖的是上一行和上一列的数据，因此我们需要从上往下，从左往右

（5）返回值

我们最后要求到达右下角的最小路径和，返回dp[m][n]

参考代码：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,201*(m*n)));dp[0][1] = 0;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]) + grid[i-1][j-1];return dp[m][n];   }
};

🏠 地下城游戏

📌 题目解析

174. 地下城游戏 - 力扣（LeetCode）

📌 算法原理

（1）状态表示

按照我们之前的经验结合题目要求，我们可能会将状态设置为从起点出发，到达(i,j)位置所需的最低初始健康点数。但是该状态是行不通的，因为你这个状态是需要基于上方和左方的状态推导除了，你虽然满足了上方和左方到达该位置，但是你后续前进的时候可能game over，这里的最低初始健康点数指的是保底你能通关拯救公主的最低点数！

既然正着不行我们反着来，定义dp[i][j]为从(i,j)位置出发，到达终点所需的最低初始健康点数。

（2）状态转移方程

从最近一步出发，我们要么向下走，要么向右走,求(i,j)位置状态需要知道(i+1,j)和(i,j+1)两个位置状态的最小值，再减去自身，如果自身位置是负数的话，我们的初始点数需要能抵消这个点数，是正数的话，那我们的初始点数还能再低点。

因此，dp[i][j] = min(dp[i+1][j],dp[i][j+1]) - g[i][j]。但是注意一个特殊情况，如果遇到你位置是一个很大的血包的话(即g[i][j]是个很大的正数)，你可能会被减成负数，这不符合实际，你即使有大血包，但是你需要先到达这个位置，也就是到达该位置时最少点数为1

因此我们需要处理这种特殊情况：dp[i][j] = max(1,dp[i][j])

（3）初始化

由于虚拟结点是扩充在最后一列和最后一行,此时不需要担心访问原数组时的下标映射问题.

(4) 填表顺序

由状态转移方程得知,我们依赖(i+1,j)和(i,j+1)位置的状态,因此我们应该从下往上每一行,从右往左

(5) 返回值

根据我们定义的状态表示,我们最终返回dp[0][0]即可

参考代码:

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size();int n = dungeon[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));dp[m-1][n] = dp[m][n-1] = 1;for(int i = m-1 ; i>= 0 ;i--)for(int j = n-1 ; 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. 对于路径问题定义状态,我们一般是选取某一个位置分析,可以是从该位置出发,也可以是从该位置为结尾,如果一种问题不行,我们要尝试改变状态

2. 对于虚拟结点的设置,我们需要考虑后续填表正确以及是否影响下标映射的问题