题目
题意：每个格子里都有数字，负数代表你会少血，正数代表你会加血，当你的血量为0的时候就死了，从左上角出发，到右下角，问你一开始最少的血量是多少。整个过程中不能有血量为0的情况。
题解：只能走下或者走右。这种有向无环图，八成都是动态规划。但是如果从左上角开始规划，有很多情况要考虑。从右下角开始规划，才可以。
dp[i][j]代表从i,j到右下角，最低需要多少血量。
代码语言：javascript复制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);
}
};
