資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
