Keshawn_lu's Blog

Leetcode 174. 地下城游戏

动态规划
字数统计: 914阅读时长: 3 min
2020/07/12 Share

题目简介：

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

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

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

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

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

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

-2 (K) -3 3
-5 -10 1
10 30 -5 (P)

说明:

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

思路：

动态规划，dp[i][j]代表从该点出发到达终点，所需要的最低初始健康点数。

一开始想的是从前往后遍历进行动态规划，但是这样子在过程中我们需要记录：

  1. 从出发点到当前点的路径和
  2. 从出发点到当前点所需的最小初始值

但是这样子会出现矛盾的情况，无法判断哪条路是最佳的，会影响后续的决策。

所以采用了从终点向前进行遍历，这样子只需考虑最小初始值就可以了。

定义一个choose = min(dp[i + 1][j], dp[i][j + 1])，即选取小的初始值。

若choose - dungeon[i][j] > 0，则dp[i][j] = choose - dungeon[i][j]。

若choose - dungeon[i][j] <= 0，说明dungeon[i][j]这个房间增加的健康点数大于等于到达终点的所需健康点数，所以若从该点出发，初始健康值取最小即可，即dp[i][j] = 1。

最后返回dp[0][0]即可。

tip:

  • 首先初始化最后一行和最后一列，排除边界问题。

代码如下：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {

        vector<vector<int>> dp(dungeon.size(), vector<int>(dungeon[0].size(), 0));

        int m = dungeon.size();
        int n = dungeon[0].size();

        if(dungeon[m - 1][n - 1] >= 0)
            dp[m - 1][n - 1] = 1;
        else
            dp[m - 1][n - 1] = abs(dungeon[m - 1][n - 1]) + 1;

        for(int i = dungeon.size() - 2; i >= 0; i--){

            if(dp[i + 1][n - 1] - dungeon[i][n - 1] > 0)
                dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i][n - 1];
            else
                dp[i][n - 1] = 1;
        }

        for(int j = dungeon[0].size() - 2; j >= 0; j--){

            if(dp[m - 1][j + 1] - dungeon[m - 1][j] > 0)
                dp[m - 1][j] = dp[m - 1][j + 1] - dungeon[m - 1][j];
            else
                dp[m - 1][j] = 1;
        }

        for(int i = dungeon.size() - 2; i >= 0; i--){

            for(int j = dungeon[i].size() - 2; j >= 0; j--){

                int choose = min(dp[i + 1][j], dp[i][j + 1]);

                if(choose - dungeon[i][j] > 0)
                    dp[i][j] = choose - dungeon[i][j];
                else
                    dp[i][j] = 1;
            }
        }

        return dp[0][0];
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网