【动态规划2】路径问题
动态规划在解决路径问题时非常常见，特别是在图论和网络优化问题中。一般来说，动态规划用于解决那些具有重叠子问题和最优子结构性质的问题。路径问题通常涉及找到从起点到终点的最佳路径，可以是最短路径、最长路径或者满足特定条件的路径等。
那么可能会问，为啥不用深度搜索呢？因为深度搜索有时候会超时，因此用动态规划。
在动态规划不同路劲问题中，遇到的数组大部分可能是一个二维数组，因为是在图中。
下面是小编在做动态规划时，总结的一些关于不同路劲的一些习题思路，仅供参考，如有误，请指出！！
62. 不同路径
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7 输出：28
示例 2： 输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右
- 向下 -> 向右 -> 向下
示例 3： 输入：m = 7, n = 3 输出：28
示例 4： 输入：m = 3, n = 3 输出：6
分析
- 状态表示：dp[i][j]表示到达[i,j]时有多少种方式
- 状态转移方程：如下图所示，三角形位置为[i,j]，可以从[i-1,j]位置或者[i,j-1]位置到达三角形位置，dp[i - 1][j]是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。那么很，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
- 初始化 有两种初始化的方式： 第一种是直接第一列和第一行初始化成1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;第二种： 分别给列和行多加一列，并且dp[0][1]位置初始化为1，其余位置初始化为1，这样，在后续遍历就可似的第一行和第一列为1
- 填表顺序： 从上往下，从左往右
- 返回值： 返回dp[m][n]的值
代码
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];
}
};63. 不同路径 II
63.不同路径 II添加链接描述
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
分析
- 状态表示：dp[i][j]表示到达[i,j]时有多少种方式
- 状态转移方程：如下图所示，三角形位置为[i,j]，可以从[i-1,j]位置或者[i,j-1]位置到达三角形位置，dp[i - 1][j]是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。那么很，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。但是当有障碍物的时候，方法就为0。
- 初始化 有两种初始化的方式： 第一种是直接第一列和第一行初始化成1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;第二种： 分别给列和行多加一列，并且dp[0][1]位置初始化为1，其余位置初始化为1，这样，在后续遍历就可似的第一行和第一列为1
- 填表顺序： 从上往下，从左往右
- 返回值： 返回dp[m][n]的值
代码
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m=obstacleGrid.size(),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]==0)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[m][n];
}
};剑指Offer47.礼物的最大价值
题目描述
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
只能从架子的左上角开始拿珠宝 每次可以移动到右侧或下侧的相邻位置 到达珠宝架子的右下角时，停止拿取 注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
示例 1: 输入: frame = [[1,3,1],[1,5,1],[4,2,1]] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
分析
- 状态表示：dj[i][j]表示到达[i,j]时的最大价值
- 状态转移方程：可以从[i-1,j]位置或者[i,j-1]位置到达[i,j]位置，但是dp[i][j]表示的价值，因此还要加上[i,j]位置上的价值，因此dp[i][j]=dp[i-1][j]+frame[i][j]和dp[i][j]=dp[i][j-1]+frame[i][j]，两者取最大值。
- 初始化：分别给列和行多加一列，并且初始化都为0。
- 填表顺序： 从上往下，从左往右
- 返回值： 返回dp[m][n]的值
代码
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m=frame.size(),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],dp[i][j-1])+frame[i-1][j-1];
}
}
return dp[m][n];
}
};931.下降路径最⼩和
题目描述
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1：
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：如图所示，为和最小的两条下降路径
示例 2：
输入：matrix = [[-19,57],[-40,-5]] 输出：-59
分析
- 状态表示：dp[i][j] 表⽰：dp[i][j] 表⽰：到达 [i, j] 位置时，所有下降路径中的最⼩和
- 状态转移方程： 对于普遍位置 [i, j] ，根据题意得，到达 [i, j] 位置可能有三种情况： i. 从正上⽅[i - 1, j] 位置转移到[i, j] 位置； ii. 从左上⽅ [i - 1, j - 1] 位置转移到 [i, j] 位置； 比特就业课iii. 从右上⽅[i - 1, j + 1] 位置转移到 [i, j] 位置； 我们要的是三种情况下的「最⼩值」，然后再加上矩阵在 [i, j] 位置的值。 于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j +1])) + matrix[i][j]
- 多加一行，在第一列前加一列，最后一列后面加一列，因此加两列
- 填表顺序：从上往下
- 返回值：这里不是直接返回dp[n][n]，因为题目说只要返回到最后一行就行，因此需要返回dp表中最后一行的最小值
代码
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n=matrix.size();
vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));
for(int j=0;j<n+2;j++) dp[0][j]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i-1][j-1];
}
}
int ans=INT_MAX;
for(int j=1;j<=n;j++) ans=min(dp[n][j],ans);
return ans;
return dp[n][n];
}
};64.最⼩路径和
题目描述
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
示例 2： 输入：grid = [[1,2,3],[4,5,6]] 输出：12
代码
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
dp[0][1]=dp[1][0]=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.地下城游戏
题目描述
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2： 输入：dungeon = [[0]] 输出：1
代码
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m=dungeon.size(),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];
}
};腾讯云开发者
