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