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