一道关于骑士救公主故事的题目。

一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快到达公主,骑士决定每次只向右或向下移动一步。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/dungeon-game

分析

这与之前的那道 64.最短路径和 颇为相似,不同的是,最短路径和是从左上角开始,取右&下最小一直算到右下角。而本题如果如法炮制(左上->右下)的话,并不能得到最初的最小健康点。

要算开始点的最小健康点,应该从右下->左上求值。对于这样的最优路径题目,我们一贯采用DP来解。

算法

1. 首先初始化一个二维数组DP[M+1][ N+1]值都是INT_MAX(额外的一行一列是为了确定DP中最后一行和最后一列使用的,当然你也可以不用额外的行列,首先算出右下角的数值,单独算最后一行和最后一列);

2. 从DP右下角[M][N]开始,一直算到左上角

状态方程:

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

dp[i][j] = ans; (ans >0)

dp[i][j] = 1; (else)

3. 输出dp[0][0]

解释:我们根据当前点的右边和下边点来确定当前点。由于要求最小的生命值/健康点,所以我们取二者中的最小值(可以认为下一步的生命值越小,本点的生命值就越小)减去当前点(i, j)的损耗值,就是本点的最小生命值。(在简单点儿说就是,上一点的初始PH+损耗PH(有正有负) = 下一点初始PH,我们算的都是初始PH值,所以用下一点的初始PH-损耗=上一点的初始PH)

源码1 二维DP

 1 class Solution {
 2 public:
 3     int calculateMinimumHP(vector<vector<int>>& dungeon) {
 4         int row = dungeon.size();
 5         int col = dungeon[0].size();
 6         if(row == 0 || col == 0)
 7             return 1;
 8         vector<vector<int>> dp(row+1, vector<int>(col+1, INT_MAX));
 9         dp[row][col-1] = 1; dp[row-1][col] = 1;
10         for(int i=row-1; i>=0; i--)
11         {
12             for(int j=col-1; j>=0; j--)
13             {
14                 int ph = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
15                 dp[i][j] = (ph > 0)?ph:1;
16             }
17         }
18         return dp[0][0];
19     }
20 };

源码2 原地操作,不使用额外空间

 1 class Solution {
 2 public:
 3     int calculateMinimumHP(vector<vector<int>>& dungeon) {
 4         int row = dungeon.size();
 5         int col = dungeon[0].size();
 6         if(row == 0 || col == 0)
 7             return 1;
 8      //右下角点PH值
 9         dungeon[row-1][col-1] = sub(1, dungeon[row-1][col-1]);
10         //最后一行/一列单独计算
11         for(int i=row-2; i>=0; i--)
12             dungeon[i][col-1] = sub(dungeon[i+1][col-1], dungeon[i][col-1]);
13         for(int i=col-2; i>=0; i--)
14             dungeon[row-1][i] = sub(dungeon[row-1][i+1], dungeon[row-1][i]);
15         //其他点计算
16         for(int i=row-2; i>=0; i--)
17         {
18             for(int j=col-2; j>=0; j--)
19             {
20                 dungeon[i][j] = sub(min(dungeon[i+1][j], dungeon[i][j+1]), dungeon[i][j]); 
21             }
22         }
23         return dungeon[0][0];
24     }
25     //用于计算当前点的初始PH,参数为min(右边,下边),当前点损耗值
26     int sub(int ph, int sub)
27     {
28         int PH = ph - sub;
29         return (PH > 0) ? PH : 1;
30     }
31 };

源码3 使用一维DP数组

自己尝试吧!没有必要!