[动态规划] (十) 路径问题 LeetCode 174.地下城游戏

[动态规划] (十) 路径问题: LeetCode 174.地下城游戏

174. 地下城游戏

题目解析

先明白下题题再来看。

[动态规划] (四) LeetCode 91.解码方法-CSDN博客

(1) 骑士拯救公主：从左上角到右下角

(2) 每个格子都是一个房间，房间内有恶魔或者魔法球

(3) 恶魔扣除血量，魔法球增加血量

(4) 骑士只能向右或者向下移动

(5) 血量小于等于0，骑士死亡

(6) 返回拯救公主，最少需要的血量

解题思路

状态表示

按照以往的经验，我们都是设定以(i，j)位置为终点所需要的最低血量，但是这道题不太方便。

示例1：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]

假如一开始，你设定最小血量为3。

• 第一次，3 - 2 => 1-3 => -2，又得回去修改初始血量为6，
• 第二次，6-2-3=> 1+3+1=>5-5 = 0，又回去设定初始血量为7，
• 第三次，7-2-3+3+1 => 6-5=>1 ，终于救出了公主。

这种情况有个专业的名词，后置性。(想要了解大家可以去自行查资料)

总之，这种方法很难实现，所以我们选择第二种方法。

以(i，j)为起点到达终点所需要的最低血量，即dp[i] [j]。

状态转移方程

从(i，j)位置到下一步，也就是到达(i，j+1)或者(i+1，j)位置。

所以到达(i，j)位置后加上当前位置的值dungeon(i,，j)，必须大于等于下一位置的值。

即骑士到达(i，j)位置，击败(i，j)位置上的恶魔后，血量必须大于击败下一个恶魔所消耗的血量。也就是如上图，骑士击败-2位置的恶魔后的血量，必须大于-3，也就是等于6。

dp[i][j] + dungeon[i][j] >= min(dp[i][j+1], dp[i+1][j])
1

当然，房间内也有可能是魔法球(加血)，到达dp[i] [j]前有可能血量已经小于等于0了，我们必须让它的最小值是1即可。

即骑士到达(i，j)位置，获得(i，j)位置上的魔法球前血量必须最小为1。

如上图，骑士接连击败-2，-3恶魔后还得有1滴血来获得魔法球。

为了不让dp[i] [j]为负数，

dp[i][j] = max(1, dp[i][j])
1

初始化和填表顺序

• 初始化

我们访问的是j+1、i+1的位置，所以一般从右下角开始初始化。

和以往不同，我们初始化时，与1-6号位置有边界情况，如图。

1号位置与右边和下边的位置有影响，让它初始化为1，即可保证击败公主位置上的恶魔后至少还有1滴血。

2、3、4、5、6等位置的下边或者旁边，因为多了一行或者一列，为了不让骑士走出恶魔的城堡，初始化为整数的最大值即可。

• 填表顺序

倒着一列一列填表即可，参考状态表示，一步一步推出上一位置所需要的最少血量，直到(0，0)位置。

返回值

返回(0，0)位置即可，与我们得出的状态表示相同。

看到这里，大家可以尝试实现一下代码，然后再看后面的内容。

---

代码实现

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        //创建一个dp数组
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX));
        //初始化
        dp[m-1][n] = dp[m][n-1] = 1;
        //填表
        for(int i = m-1; i >= 0; i--)
            for(int j = n-1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j];
                dp[i][j] = max(1, dp[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

总结

细节1：我们的下标对应的原数组并没有因为我们扩大一列和一行而改变，因为我们扩大的是最后一列最后一行。

细节2：走到下一位置时至少还要保证有1滴血，若是血量 <= 0，让它至少要为1滴血，否则无法进入下一个房间。