題目
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
Notes:
The knight's health has no upper bound.
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
解題之法
class Solution {
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
int dp[m][n];
dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
for (int i = m - 2; i >= 0; --i) {
dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
}
for (int j = n - 2; j >= 0; --j) {
dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
}
for (int i = m - 2; i >= 0; --i) {
for (int j = n - 2; j >= 0; --j) {
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
}
}
return dp[0][0];
}
};
分析
這道王子救公主的題還是蠻新穎的，我最開始的想法是比較右邊和下邊的數(shù)字的大小豌鸡，去大的那個嘿般，但是這個算法對某些情況不成立段标，比如下面的情況：
1 (K) -3 3
0 -2 0
-3 -3 -3 (P)
如果按我的那種算法走的路徑為 1 -> 0 -> -2 -> 0 -> -3, 這樣的話騎士的起始血量要為5，而正確的路徑應(yīng)為 1 -> -3 -> 3 -> 0 -> -3, 這樣騎士的騎士血量只需為3博个。無奈只好上網(wǎng)看大神的解法怀樟，發(fā)現(xiàn)統(tǒng)一都是用動態(tài)規(guī)劃Dynamic Programming來做，建立一個和迷宮大小相同的二維數(shù)組用來表示當(dāng)前位置出發(fā)的起始血量盆佣，最先初始化的是公主所在的房間的起始生命值往堡，然后慢慢向第一個房間擴散，不斷的得到各個位置的最優(yōu)的起始生命值共耍。遞歸方程為: 遞歸方程是dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
