leetcode174. 地下城游戏/动态规划

题目：174. 地下城游戏

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

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

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

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

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如：

考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7
 
1
2

说明:

• 骑士的健康点数没有上限。

• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dungeon-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想：动态规划

• dp[i][j]：到达[i,j]所需的最小健康数
• 状态：每一个位置
• 选择：逆向dp，从下面到达该位置，从右面到达该位置
• 状态转移方程：$$dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);$$

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int row = dungeon.size();
        int col = dungeon[0].size();
        if(dungeon.size() == 0)
            return 0;
        vector<vector<int>> dp(dungeon.size(), vector<int>(dungeon[0].size(), 0));
        
        //从左下到右上dp
        for(int i = row - 1; i >= 0; --i){
            for(int j = col - 1; j >= 0; --j){
                if(i == row - 1){//最后一行
                    if(j == col - 1)
                        dp[i][j] = max(1, 1 - dungeon[i][j]);
                    else{
                        dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j]);
                    }
                }
                else if(j == col - 1){
                    dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j]);
                }
                else{
                    dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
                }
              
            }
        }
        
        return dp[0][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

说明：当初采用的正向dp，同时记录到达该点的所需健康数，以及所积存的能量，每次选择时选取所需健康数小的作为转移，但是有可能选取健康数小，但能量大的作为转移会使得最终的健康数小。因此，两种条件同等重要，无法利用正向dp实现。