【题意】

给定m*n的地牢，王子初始位置在左上角，公主在右下角不动，王子要去救公主，每步只能往右或往下走一格。每个格子是一个整数，负数代表生命值减掉相应分数，正数表示生命值增加相应分值，要保证王子在走的过程中不挂掉，即经过每个格子后的生命值大于等于1，问王子最初的生命值最少是多少。

【思路】

倒着推dp，计算(i,j)->(m,n)的可生存血量。

dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-a[i][j]]);

【AC】

1 class Solution { 2 public: 3     int calculateMinimumHP(vector
      
       
        >& dungeon) { 4         int m=dungeon.size(); 5         int n=dungeon[0].size(); 6         const int inf=0x3f3f3f3f; 7         vector
        
         
           > dp(m+1,vector
          
           (n+1)); 8         for(int i=0;i<=m;i++){ 9             for(int j=0;j<=n;j++){10                 dp[i][j]=inf;11             }12         }13         dp[m-1][n-1]=max(1,1-dungeon[m-1][n-1]);14         for(int k=m+n-3;k>=0;k--){15             for(int i=0;i
           
            =n) continue;18 dp[i][j]=max(1,min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]);19 }20 }21 return dp[0][0];22 }23 };