https://leetcode.com/problems/dungeon-game/
喜歡做這種有情節(jié)的題目。
6.4就要做indeed筆試糊治，現(xiàn)在心情比較激動。
最近玩的Dragon Hills已經(jīng)過到了level70。
1.右下到左上镀岛，常規(guī)解法
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector<vector<int> > dp(m, vector<int>(n, 1));
//init
dp[m-1][n-1] = dungeon[m-1][n-1] >= 0 ? 1 : - dungeon[m-1][n-1] + 1;
for(int i = n-2; i >= 0; i--)
dp[m-1][i] = dungeon[m-1][i] >= dp[m-1][i+1] ? 1 : dp[m-1][i+1] - dungeon[m-1][i];
for(int i = m-2; i >= 0; i--)
dp[i][n-1] = dungeon[i][n-1] >= dp[i+1][n-1] ? 1 : dp[i+1][n-1] - dungeon[i][n-1];
//dp
for(int i = m-2; i >= 0; i--) {
for(int j = n-2; j >= 0; j--) {
int d = min(dp[i][j+1],dp[i+1][j]);
if(dungeon[i][j] >= d)
dp[i][j] = 1;
else
dp[i][j] = d - dungeon[i][j];
}
}
return dp[0][0];
}
};
2.壓縮了一行空間
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
int n = dungeon[0].size();
vector<int> dp(n, 1);
//init
dp[n-1] = dungeon[m-1][n-1] >= 0 ? 1 : - dungeon[m-1][n-1] + 1;
for(int i = n-2; i >= 0; i--)
dp[i] = dungeon[m-1][i] >= dp[i+1] ? 1 : dp[i+1] - dungeon[m-1][i];
//dp
for(int i = m-2; i >= 0; i--) {
dp[n-1] = dungeon[i][n-1] >= dp[n-1] ? 1 : dp[n-1] - dungeon[i][n-1];
for(int j = n-2; j >= 0; j--) {
int d = min(dp[j+1],dp[j]);
if(dungeon[i][j] >= d)
dp[j] = 1;
else
dp[j] = d - dungeon[i][j];
}
}
return dp[0];
}
};
3.標簽里給的Binary Search
看到Dicuss里的一個Binary Search解答翔烁，覺得不是很可靠而且時間復雜度好高渺氧。
https://leetcode.com/discuss/25671/a-simple-c-solution-using-binary-search
