数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 地牢游戏
假设有一个故事，恶魔抓走了名叫 P 的公主，并把她囚禁在地牢的右下角。地牢由 M 行 N 列的网格状房间组成。我们勇敢的骑士 K 最初位于左上角的房间，必须穿越地牢去拯救公主。
现在骑士有一个初始生命值，用正整数表示。如果在任何时候他的生命值降到 0 或以下，他就会立即死亡。
一些房间有守护该房间的恶魔，因此骑士进入这些房间时会损失生命值（负整数）；其他房间要么是空的，要么包含增加骑士生命值的魔法球（正整数）。
所以如果他想尽快到达公主，骑士决定每一步只向右或向下移动。我们必须找到足以到达 P 的最小初始生命值。所以如果输入是这样的，那么答案将是 6，因为 K 可以使用路径 右 -> 右 -> 下 -> 下到达 P
| -2(k) | -2 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5p |
为了解决这个问题，我们将遵循以下步骤 -
r := dp 的行，c := dp 的列
用于初始化 j := r - 2，当 j >= 0 时，将 j 递减 1 -
dp[j, c - 1] := dp[j, c - 1] 和 dp[j, c - 1] + dp[j + 1, c - 1] 的最小值
用于初始化 j := c - 2，当 j >= 0 时，将 j 递减 1 -
dp[r - 1, j] := dp[r - 1, j] 和 dp[r – 1, j] + dp[r – 1, j + 1] 的最小值
用于初始化 i := r - 2，当 i >= 0 时，将 i 递减 1 -
用于初始化 j := c - 2，当 j >= 0 时，将 j 递减 1 -
dp[i, j] := dp[i, j] 和 dp[i, j] + dp[i + 1, j] 与 dp[i, j] + dp[i, j + 1] 的最大值的最小值
如果 dp[0, 0] <= 0，则
返回 |dp[0, 0]| + 1
返回 1
示例
让我们看看以下实现，以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli min(lli a, lli b){
return a <= b ? a : b;
}
lli max(lli a, lli b){
return a <= b ? b : a;
}
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dp) {
int r = dp.size();
int c = dp[0].size();
for(lli j=r-2;j>=0;j--){
dp[j][c-1] = min(dp[j][c-1], dp[j][c-1]+dp[j+1][c-1]);
}
for(lli j = c-2;j>=0;j--){
dp[r-1][j] =min(dp[r-1][j], dp[r-1][j]+dp[r-1][j+1]);
}
for(lli i = r-2;i>=0;i--){
for(lli j = c-2;j>=0;j--){
dp[i][j] = min(dp[i][j],max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i][j+1]));
}
}
if(dp[0][0] <= 0 )return abs(dp[0][0])+1;
return 1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
cout << (ob.calculateMinimumHP(v));
}输入
{{-2,-2,3},{-5,-10,1},{10,30,-5}}输出
6
579 次浏览
