点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃
1.最小路径和
题目链接:64. 最小路径和
题目描述:
求左上角到右上角最小路径和。注意只能向下向右移动!
算法原理:
1.状态表示
经验 + 题目要求
dp[i][j] 表示:到达 [i][j] 位置时,最小路径和
2.状态转移方程
根据最近一步,划分问题
到达[i][j]有两种情况,[i-1][j],[i][j-1]都可以到,但是我们要找的是到达 [i][j] 最小路径,那[i-1][j],[i][j-1]一定要是最小。而dp[i][j] 表示:到达 [i][j] 位置时,最小的下降路径。然后在加上[i][j]本身的值。所以状态转移方程为
3.初始化
填表时保证不越界
如果我们开辟和原数组一样大小的dp表,第一行和第一列填表的时候都会越界。因此dp表可以多开一行一列。
- 虚拟节点里面的值,要保证后面填表的结果是正确的
- 下标的映射
虚拟节点的值应该放什么呢。先不考虑多加的行和列。没有这些的话,考虑这些填表越界的格子应该填多少。先看第一个格子,第一个格子的意思是dp[0][0]表示达到[0][0]位置的最小值,那没得选就是它本身也就是之前矩阵g[0][0]的值,这个格子的值是上一个格子和左边格子的最小值在加上自己本身,因此第一个格子上面和左边虚拟格子我们给0,
剩下的虚拟格子也给0吗?不行的。如果是0,那这个虚拟格子里的值就会参与取最小值的运算。会导致填表错误。因此把剩下格子设置为+∞,只把[0][1]和[1][0]位置设置为0就好了。
当前你也可以直接把第一行和第一列初始化,但是用的更多的还是多开一行一列。
如果做的多,你会发现求最小值,就是dp表先给+∞,仅修改几个位置的值就可以了。同样求最大值,dp表先给-∞,然后修改几个位置的值就可以了。
4.填表顺序
从上到下填写每一行,每一行从左往右
5.返回值
多开一行一列右下角就变成[m][n],所以返回dp[m][n]
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
// 1.创建dp表
// 2.初始化
// 3.填表
// 4.返回值
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];
}
};
2.地下城游戏
题目链接: 174. 地下城游戏
题目分析:
骑士要从左上角出发到右下角救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。骑士每次只能向左向右移动。骑士每到一个格子要么就是减去健康点、要么加上健康点、要么不增不加。注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。也就是说到达右下角救公主也可能减去健康点。
如下面例子,第一个格子是-2,我们可以给个3 ,但是走到-3,骑士就死了。我们也就知道给3不行,然后就给个6,走到右下角骑士也死了也是不行的。因此最终给个7才真正救出公主。
算法原理:
1.状态表示
经验 + 题目要求
经验我们有两个,1.以某个位置为结尾,巴拉巴拉。 2.以某个位置为起点,巴拉巴拉。
- 以某个位置为结尾,巴拉巴拉
dp[i][j] 表示:从起点出发,到达[i][j]位置的时候,所需要的最低初始健康点数。
但是回到刚才的分析,当往下走的时候,发现骑士死了,才知道初始给的健康点数是不对。还需要重新给。显然是不行的。因此以某个位置为结尾这种经验定状态标识是不行的,所以换一种。
- 以某个位置为起点,巴拉巴拉
dp[i][j] 表示:从[i][j]位置出发,到达终点,所需最低初始健康值
2.状态转移方程
还是根据最近的一步,划分问题
以[i][j]位置起点,下一步可以向下向右走。那走到下一步的时候是不是还要保证下一步还可以往下在走啊。假设健康值是x ,然后往右走 是不是要保证 x + d[i][j] >= dp[i][j+1] ----> x >= dp[i][j+1] - d[i][j],又因为所需的是最低初始健康值,因此往右走仅需 x = dp[i][j+1] - d[i][j],同理往下走 x = dp[i+1][j] - d[i][j],又因为所需最低初始健康值所以取它们中最小值。
其实这里还可以这样理解,dp[i][j]表示 从[i][j]位置出发,到达终点,所需最低初始健康值。每次只能向右向下走,[i][j]最近一步 [i][j+1] 和 [i+1][j],那如果知道 dp[i][j+1]和dp[i+1][j] 到达终点,所需最低初始健康值,取它俩中最小,在减去 d[i][j] 健康点的情况不就是dp[i][j]到达终点,所需最低初始健康值了吗。
但是这里还有一个非常细的细节,如果dp[i][j] 等于一个负数怎么办。也就是说d[i][j] 这里是一个很大的血包,dp[i][j] 为负值 难道要一个死去的骑士要去救公主吗,显示是不合常识的,因此要处理一下。这个血包就足以骑士走接下来的路,因此给骑士一个最低的健康点 1 就行了。
3.初始化
多给一行一列,不过多给一行一列是给在下面的。所以就没有下标映射的关系了。
只关注,虚拟节点的值,要保证接下来填表正确。
骑士走到右下角救到公主之后,向右向下走还必须保证骑士活着健康点还必须是最低,因此dp[m][n-1] = dp[m-1][n] = 1,其他虚拟节点的值为了不影响dp[i][j]找最小运算直接给+∞。
4.填表顺序
从下往上,从右往左
5.返回值
dp[0][0]