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); } };