174.dungeon-game.md

174. 地下城游戏

1. 描述：

   • 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。
   • 地下城是由 M x N 个房间组成的二维网格。骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
   • 骑士的初始健康点数为一个正整数(最低是1)。如果健康点数在某一时刻降至0或以下，会立即死亡。
   • 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；
   • 其他房间要么是空的（值为0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
   • 为了尽快到达公主，骑士决定每次只向右或向下移动一步。
   • 计算确保骑士能够拯救到公主所需的最低初始健康点数。

2. 思路

   • 考虑从右下往左上进行动态规划。

     • 令dp[i][j]表示从坐标(i,j)到终点所需的最小初始值。即，当我们到达(i,j) 时，如果此时我们的路径和不小于dp[i][j]，我们就能到达终点。
     • 这样一来，我们就无需担心路径和的问题，只需要关注最小初始值。
     • 对于dp[i][j]，我们只要关心 dp[i][j+1] 和 dp[i+1][j] 的最小值 minn。
     • 记当前格子的值为dungeon(i,j)，那么在(i,j)的初始值只要达到minn−dungeon(i,j)即可。同时，初始值还必须大于等于1。

   • 得到状态转移方程：

     • dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])−dungeon(i,j),1)
     • 最终答案即为dp[0][0]。

   • 边界条件

     • 当 i=n−1或 j=m−1时，dp[i][j]转移需要用到的dp[i][j+1]和dp[i+1][j]中有 无效值，因此给无效值赋值为极大值INT_MAX。
     • dp[n-1][m-1]转移需要用到的 dp[n−1][m]和dp[n][m−1]均为无效值，因此给这两个值赋值为1。

3. 参考：https://leetcode-cn.com/problems/dungeon-game/solution/di-xia-cheng-you-xi-by-leetcode-solution/

4. 实现

   class Solution {
   public:
       int calculateMinimumHP(vector<vector<int>>& dungeon) {
           int m=dungeon.size(), n=dungeon[0].size();
           vector<vector<int>>dp(m+1,vector<int>(n+1, INT_MAX));
           dp[m][n-1]=1;
           dp[m-1][n]=1;
           for(int i=m-1; i>=0; i--){
               for(int j=n-1; j>=0; j--){
                   dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j], 1);
               }
           }
           return dp[0][0];
       }
   };