LeetCode 174. Dungeon Game(DP)
- 2020 年 2 月 14 日
- 筆記
題意：每個格子里都有數字，負數代表你會少血，正數代表你會加血，當你的血量為0的時候就死了，從左上角出發，到右下角，問你一開始最少的血量是多少。整個過程中不能有血量為0的情況。
題解：只能走下或者走右。這種有向無環圖，八成都是動態規劃。但是如果從左上角開始規劃，有很多情況要考慮。從右下角開始規劃，才可以。
dp[i][j]代表從i,j到右下角，最低需要多少血量。
class Solution { public: int dp[1005][1005]; int calculateMinimumHP(vector<vector<int>>& dungeon) { for(int i=0;i<dungeon.size();i++) { for(int j=0;j<dungeon[i].size();j++) { dp[i][j] = 99999999; } } for(int i=dungeon.size()-1;i>=0;i--) { for(int j=dungeon[i].size()-1;j>=0;j--) { if(i!=dungeon.size()-1) { if(dungeon[i][j]<0) { int x = dp[i+1][j] + dungeon[i][j]*-1; if(dp[i+1][j]==0) x ++; dp[i][j] = min(dp[i][j],x); } else { int x = (dp[i+1][j] - dungeon[i][j])<0?0:(dp[i+1][j] - dungeon[i][j]); dp[i][j] = min(dp[i][j],x); } } if(j!=dungeon[i].size()-1) { if(dungeon[i][j]<0) { int x = dp[i][j+1] + dungeon[i][j]*-1; if(dp[i][j+1]==0) x++; dp[i][j] = min(dp[i][j],x); } else { int x= (dp[i][j+1] - dungeon[i][j])<0?0:(dp[i][j+1] - dungeon[i][j]); dp[i][j]=min(dp[i][j],x); } } if(j==dungeon[i].size()-1&&i==dungeon.size()-1) { if(dungeon[i][j]<0) { dp[i][j]=dungeon[i][j]*-1 +1; } else if(dungeon[i][j]==0) { dp[i][j]=1; } else dp[i][j]=0; } } } return max(dp[0][0],1); } };
