【leetcode dp】Dungeon Game

https://leetcode.com/problems/dungeon-game/description/

【题意】

给定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】

 class Solution {

 public:

     int calculateMinimumHP(vector<vector<int>>& dungeon) {

         int m=dungeon.size();

         int n=dungeon[].size();

         const int inf=0x3f3f3f3f;

         vector<vector<int> > dp(m+,vector<int>(n+));

         for(int i=;i<=m;i++){

             for(int j=;j<=n;j++){

                 dp[i][j]=inf;

             }

         }

         dp[m-][n-]=max(,-dungeon[m-][n-]);

         for(int k=m+n-;k>=;k--){

             for(int i=;i<m;i++){

                 int j=k-i;

                 if(j<||j>=n) continue;

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

             }

         }

         return dp[][];

     }

 };

巴特西

【leetcode dp】Dungeon Game

最新文章

热门文章