地下城游戏

Category Difficulty Likes Dislikes
algorithms Hard (48.68%) 664 -
Tags

binary-search | dynamic-programming

Companies

microsoft

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

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

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

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

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

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

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

说明:

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

动态规划(c++)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem174.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=174 lang=cpp
 *
 * [174] 地下城游戏
 */

// @lc code=start
/** 
 * blood为健康值，要所有路劲最小值且大于0
 * 初始健康值为一条路径上的最小负数+1, 如果没有负数则为1
 * 动态规划边界情况：dp[col+1][row+1][2]; (dp[0][0-row] && dp[0-col][0]) = 0
 * i = 1 ~ (col - 1) j = 1 ~ (row - 1)
 * dp[i][j] = max(dp[i-1][j][0], dp[i][j-1][0]) 
 * 0   0   0   0     0   0  -I  -I        -3  -1   2   I
 * 0  -2  -3   3     0  -2  -5  -5        -29 -14  5   I
 * 0  -5  -10  1    -I  -7  -15 -5        -34 -24  6   1
 * 0   3   3  -5    -I  -7  -7  -10        I   I   1   0
 * 
 * [[1,-3,3],
 * [0,-2,0],
 * [-3,-3,-3]]
 * 
 * 左上往右下计算，无法满足动态规划。
 *
 * 
 */
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int col = dungeon.size(), row = dungeon[0].size();
        /** 
         * 左上往右下无法找到
         */
        // vector<vector<vector<int>>> dp(col+1, vector<vector<int>>(row+1, vector<int>(2, 0)));
        // for (int i = 2; i <= col; ++i) {
        //     dp[i][0][0] = -INT_MAX;
        // }
        // for (int i = 2; i <= row; ++i) {
        //     dp[0][i][0] = -INT_MAX;
        // }
        // for (int i = 1; i <= col; ++i) {
        //     for (int j = 1; j <= row; ++j) {
        //         vector<int> tmp;
        //         if (dp[i - 1][j][1] > dp[i][j - 1][1]) {
        //             tmp = dp[i - 1][j];
        //         } else if (dp[i - 1][j][1] == dp[i][j - 1][1]) {
        //                 tmp = dp[i - 1][j][0] > dp[i][j - 1][0] ? dp[i - 1][j] : dp[i][j - 1];
        //         } else {
        //             tmp = dp[i][j - 1];
        //         }
        //         dp[i][j][1] = tmp[1] + dungeon[i - 1][j - 1];
        //         dp[i][j][0] = tmp[0] < dp[i][j][1] ? tmp[0] : dp[i][j][1];
        //    }
        // }
        // return 1 - dp[col][row][0];
        vector<vector<int>> dp(col + 1, vector<int>(row + 1, INT_MAX));
        dp[col - 1][row] = dp[col][row - 1] = 1;
        for (int i = col - 1; i > -1; --i) {
            for (int j = row - 1; j > -1; --j) {
                int tmp = (dp[i + 1][j] < dp[i][j + 1] ? dp[i + 1][j] : dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = tmp > 1 ? tmp : 1;
            }
        }
        return dp[0][0];
    }
};
// @lc code=end