C ++中的地下城游戏
为了解决这个问题，我们将遵循以下步骤-
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做-
dp[i，j]：=dp[i，j]的最小值，dp[i，j]+dp[i+1，j]和dp[i，j]+dp[i，j+1]的最大值
用于初始化j：=c-2，当j>=0时，将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