企业网站要更新文章吗,手机网站制作方案,专业网站建设的意义,数据处理网站开发目录
62.路径问题
解法#xff08;动态规划#xff09;#xff1a;
1. 状态表⽰#xff1a;
2. 状态转移⽅程#xff1a;
3. 初始化#xff1a;
4. 填表顺序#xff1a;
5. 返回值#xff1a;
不同路径2.0
解法#xff08;动态规划#xff09;#xff1a; …目录
62.路径问题
解法动态规划
1. 状态表⽰
2. 状态转移⽅程
3. 初始化
4. 填表顺序
5. 返回值
不同路径2.0
解法动态规划
1. 状态表⽰
2. 状态转移
3. 初始化
4. 填表顺序
5. 返回值
代码
剑指Offer47.礼物的最⼤价值
方程;
代码
931.下降路径最小和 代码
64.最小路径和
【困难题】 174.地下城游戏视频讲解
总结 62.路径问题 解法动态规划
算法思路 1. 状态表⽰
对于这种「路径类」的问题我们的状态表⽰⼀般有两种形式 i. [i, j] 位置出发巴拉巴拉ii. 从起始位置出发到达[i, j] 位置巴拉巴拉。 这⾥选择第⼆种定义状态表⽰的⽅式 dp[i][j] 表⽰⾛到[i, j] 位置处⼀共有多少种⽅式。 2. 状态转移⽅程
简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数那么到达[i, j] 位置之 前的⼀⼩步有两种情况 i. 从[i, j] 位置的上⽅ [i - 1, j] 的位置向下⾛⼀步转移到[i, j] 位置ii. 从[i, j] 位置的左⽅ [i, j - 1] 的位置向右⾛⼀步转移到[i, j] 位置。 由于我们要求的是有多少种⽅法因此状态转移⽅程就呼之欲出了 dp[i][j] dp[i - 1] [j] dp[i][j - 1] 。 3. 初始化
可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」ii. 「下标的映射关系」。 在本题中「添加⼀⾏」并且「添加⼀列」后只需将dp[0][1] 的位置初始化为1 即可。
4. 填表顺序
根据「状态转移⽅程」的推导来看
填表的顺序就是「从上往下」填每⼀⾏在填写每⼀⾏的时候 「从左往右」。
5. 返回值
根据「状态表⽰」我们要返回dp[m][n] 的值。
代码
class Solution
{
public:int uniquePaths(int m, int n){vectorvectorint dp(m 1, vectorint(n 1, 0)); // 创建⼀个 dp表 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.0 解法动态规划
算法思路 本题为不同路径的变型只不过有些地⽅有「障碍物」只要在「状态转移」上稍加修改就可解决。
1. 状态表⽰
对于这种「路径类」的问题我们的状态表⽰⼀般有两种形式 i. [i, j] 位置出发巴拉巴拉ii. 从起始位置出发到达[i, j] 位置巴拉巴拉。 这⾥选择第⼆种定义状态表⽰的⽅式 dp[i][j] 表⽰⾛到[i, j] 位置处⼀共有多少种⽅式。 2. 状态转移
简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数那么到达[i, j] 位置之 前的⼀⼩步有两种情况 i. 从[i, j] 位置的上⽅ [i - 1, j] 的位置向下⾛⼀步转移到[i, j] 位置ii. 从[i, j] 位置的左⽅ [i, j - 1] 的位置向右⾛⼀步转移到[i, j] 位置。但是 [i - 1, j] 与[i, j - 1] 位置都是可能有障碍的此时从上⾯或者左边是不可能 到达[i, j] 位置的也就是说此时的⽅法数应该是0。 由此我们可以得出⼀个结论只要这个位置上「有障碍物」那么我们就不需要计算这个位置上的 值直接让它等于0 即可。
3. 初始化
可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」ii. 「下标的映射关系」。 在本题中「添加⼀⾏」并且「添加⼀列」后只需将dp[0][1] 的位置初始化为1 即可。
4. 填表顺序
根据「状态转移⽅程」的推导来看
填表的顺序就是「从上往下」填每⼀⾏在填写每⼀⾏的时候 「从左往右」。
5. 返回值
根据「状态表⽰」我们要返回dp[m][n] 的值。
代码
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint ob) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m ob.size(), n ob[0].size();vectorvectorint dp(m 1, vectorint(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];}
};测试 剑指Offer47.礼物的最⼤价值 方程;
对于dp[i][j] 我们发现想要到达[i, j] 位置有两种⽅式 i. 从[i, j] 位置的上⽅[i - 1, j] 位置向下⾛⼀步此时到达[i, j] 位置能 拿到的礼物价值为dp[i - 1][j] grid[i][j] ii. 从[i, j] 位置的左边[i, j - 1] 位置向右⾛⼀步此时到达[i, j] 位置能 拿到的礼物价值为dp[i][j - 1] grid[i][j] 我们要的是最⼤值因此状态转移⽅程为 dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j] 。 代码
class Solution {
public:int jewelleryValue(vectorvectorint frame) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回结果int m frame.size(), n frame[0].size();vectorvectorint dp(m 1, vectorint(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.下降路径最小和 代码
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回结果int n matrix.size();vectorvectorint dp(n 1, vectorint(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 - 1], min(dp[i - 1][j], dp[i - 1][j 1])) matrix[i - 1][j - 1];//每次只能min两个int ret INT_MAX;for (int j 1; j n; j)ret min(ret, dp[n][j]);return ret;}
};64.最小路径和 代码
class Solution {
public:int minPathSum(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dp(m 1, vectorint(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要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 代码
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {if (dungeon.empty() || dungeon[0].empty()) {return 0;}int m dungeon.size(), n dungeon[0].size();vectorvectorint dp(m 1, vectorint(n 1, INT_MAX));dp[m][n-1] dp[m-1][n] 1; //假设为1因为后面要取正数的for (int i m - 1; i 0; --i) {for (int j n - 1; j 0; --j) {int minHealth min(dp[i1][j], dp[i][j1]) - dungeon[i][j];dp[i][j] max(1, minHealth);}}return dp[0][0];}
};困难题还是有困难的原因的qwq leetcode 地下城游戏 的一个问题理解 还有一点就是 dp[m][n-1] dp[m-1][n] 1
可以理解为他救完公主之后还要有一点血才能活着
总结
