動的計画法では、dp[i][j]を使って、i行j列のグリッドを終点に到達させるのに必要な最小の初期値を表します。この問題は、左上から右下に再帰的にプッシュする場合、出発点から現在位置までの経路と、出発点から現在位置までの経路に必要な最小の初期値の両方を記録する必要があり、より面倒です。
従って、右下から左上へ再帰することが可能で、各格子は現在位置から出発点までの最小の初期値のみを維持すればよく、最終的なdp[0][0]が答えとなります。
For each dp[i][j], it is related only to dp[i][j + 1], dp[i + 1][j], dungeon[i][j], if min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j] is positive then dp[i][j] is min(dp[i][j + 1], dp[i][i][j]) - dungeon[i][j], indicating that from the departure as long as there are not less than min(dp[i][j + 1], dp[i][j]) - dungeon[i][j], it means that from the departure as long as there are not less than min(dp[i][j][j]), it means that from the departure as long as there are not less thandp[i+1][j])-dungeon[i][j]、つまり騎士はスタート地点からmin(dp[i][j+1], dp[i+1][j])-dungeon[i][j]以上のライフがある限り右下に到達することができるということです。
なぜ min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j] なのですか？ この式は、dungeon[i][j]の血を引くことによって、騎士が右下に行くのに必要な最小限の血の量min(dp[i][j +1], dp[i+1][j])だけで済むグリッドに行けると言っているのです。
しかしmin(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]は負数か0かもしれません。[j], 1);
境界状態については、最後の行と最後の列は、dp[i][j + 1]とdp[i + 1][j]が両方とも存在しないので、行を1つ、列を1つ増やして配列を開き、dp[i][j]を持つ格子の最後の行の次の行と最後の列の次の列をINT_MAXとして代入します。状態移行の方程式は、dpの値の次の行と次の列の最小値を取ることなので、INT_MAXとして代入できます。つまり、INT_MAXとして代入できます。
また、右下のグリッドについては、dp[i][j + 1]、dp[i + 1][j]がともに INT_MAX であり、かつ dungeon[i][j]が負である場合、オーバーフローすることを考慮して、右下の dp[i][j + 1]、dp[i + 1][j]にともに 1 を代入し、dungeon[i][j]のライフ値を差し引いてもまだ1グリッドのライフ値が残っていることを示し、さらに左への再帰がオーバーフローしないようにします。の値を引くと、まだ1フレームのライフが残っているので、左上への再帰はオーバーフローしません。
コードは以下の通り：
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int rows = dungeon.size(), cols = dungeon[0].size(); //行と列の数
vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, INT_MAX)); //追加の行と列を開く
dp[rows - 1][cols] = dp[rows][cols - 1] = 1; //右下のグリッドの次の行と列は、オーバーフローしないように、最初に1が代入される。
for(int i = rows - 1; i >= 0; --i) {
for(int j = cols - 1; j >= 0; --j) {
dp[i][j] = max(min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j], 1);
}
}
return dp[0][0];
}
};
