leetcode：174. 地下城游戏_leetcode174

题目来源

• leetcode：174. 地下城游戏

题目描述

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon){
    
    }
};
1
2
3
4
5
6

题目解析

DFS

• 题目求骑士出发时所需要的最小生存血量，它走过一个点就会加上该点的权重（有正有负）
• 每次有两种选择，向下，向右
• 可以用递归够：
  • “嗨，dfs函数，帮我算出：如果我走右边的点，我至少要带多少安全血量”
  • “嗨，dfs函数，帮我算出：如果我走下边的点，我至少要带多少安全血量”
  • “我根据上面的返回值，算出：走到我当前的点，我至少要带的安全血量”

class Solution {
    //  返回：来到点(i,j)至少要带多少血量
    int minSaveDp(vector<vector<int>>& dungeon, int i, int j){
        int m = dungeon.size(), n = dungeon[0].size();
        
        if(i == m - 1 && j == n - 1){
            // 当来到公主坐标，如果它的权重为正，以1的血量来到这里即可
            // 如果它的权重为负，则要带着 1-dungeon[i][j] 的血量来这
            return dungeon[i][j] > 0 ? 1 : 1 - dungeon[i][j];
        }
        
        int goDown = INT32_MAX, goRight = INT32_MAX;
        // 走下方的点，需要带着的最小安全血量
        if(i < m - 1){
            goDown = minSaveDp(dungeon, i + 1, j);
        }
        // 走右方的点，需要带着的最小安全血量
        if(j < n - 1){
            goRight = minSaveDp(dungeon, i, j + 1); 
        }
        // 如果走下方，所需要带的血量更少
        if(goDown < goRight){
            if (goDown - dungeon[i][j] <= 0) {
                // goDown血量，是来到(i+1,j)的稳妥血量，等于，来到(i,j)的稳妥血量 + dungeon[i][j]
                // 则，goDown血量-dungeon[i][j]，就是来到(i,j)点的稳妥血量，如果 <= 0
                // 则要它返回 1，即来到(i,j)点的稳妥血量至少要为 1
                return 1;
            } else {
                // goDown血量，是来到(i+1,j)的稳妥血量，等于，来到(i,j)的稳妥血量 + dungeon[i][j]
                // 则，goDown血量-dungeon[i][j]，就是来到(i,j)点的稳妥血量，如果 > 0
                // 则它是安全的，返回它本身即可，即 goDown血量 - dungeon[i][j]
                return goDown - dungeon[i][j];
            }
        }else{
            if (goRight - dungeon[i][j] <= 0) {
                return 1;
            } else {
                return goRight - dungeon[i][j];
            }
        }
    }
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon){
        return minSaveDp(dungeon, 0, 0);  // 至少需要带着多少血量来到(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
33
34
35
36
37
38
39
40
41
42
43
44
45
46

动态规划

分析

• 如果按照从左上往右下的顺序进行动态规划，对于每一条路径，我们需要同时记录两个值：
  • 第一个是【从出发点到当前点的路径和】
  • 第二个是【从出发点到当前点需要的最小初始值】
• 这两个值的重要程度相同。

举个例子：

从 (0,0)到 (1,2) 有多条路径，我们取其中最有代表性的两条：

• 绿色路径[从出发点到当前点的路径和]为1，[从出发点到当前点所需的最小初始值]为3
• 蓝色路径[从出发点到当前点的路径和]为-1，[从出发点到当前点所需的最小初始值]为2

我们希望[从出发点到当前点的路径和]尽可能大，而[从出发点到当前点所需的最小初始值]尽可能小。这两条路径各有优缺点。

在上图中，我们知道应该选取绿色路径，因为蓝色路径的路径和太小，使得蓝色路径需要增大初始值到 4才能走到终点，而绿色路径只要 3 点初始值就可以直接走到终点。但是如果我们把终点的-2换成0，蓝色路径只需要初始值2，蓝色路径仍需要初始值3，最优决策就变成蓝色路径了。

因此，如果我们按照从左上到右下的顺序进行动态规划，我们就无法直接确定到达 (1,2)的方案，因为有两个重要程度相同的参数同时影响后继的决策。这就是说，这样的动态规划无法满足[无后效性]的。

于是我们考虑从右下往左上进行动态规划。

• 令dp[i][j]表示从坐标[i，j]到达终点所需要的最小初始血量。
• 从底往上走，[i，j]与[i+1，j]和[i，j+1]有关，这两个点，哪个点需要的初始值小，从[i，j]出发就选择哪一个，当前位置的值是dungeon[i][j]，需要减去这个值，也就是min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]，但是每一步的体力值至少为1。因此：$dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1)$
• 返回dp[0][0]即答案

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = 1; dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                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

我们可以对空间进行优化，使用一个一维的 dp 数组，并且不停的覆盖原有的值，参见代码如下：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<int> dp(n + 1, INT_MAX);
        dp[n - 1] = 1;
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

类似题目