动态规划帮我通关了《魔塔》

174. 地下城游戏 https://leetcode.cn/problems/dungeon-game

174. Dungeon Game https://leetcode.com/problems/dungeon-game

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
174. Dungeon Game	🔴

Prerequisites

Before reading this article, you need to learn:

• Dynamic Programming Core Framework

"Magic Tower" is a classic dungeon-style game where you lose health when encountering monsters, gain health by drinking potions, collect keys, and progress through levels to eventually rescue the beautiful princess.

You can still play this game on mobile devices:

Ah, this game surely brings back childhood memories for many. Remember those days when one person played with a game console while two or three others stood around, pointing and shouting instructions? This often made the player's experience quite miserable, while those on the sidelines had a great time 😂

LeetCode problem #174 "Dungeon Game" is a similar challenge:

174. Dungeon Game | 力扣 | LeetCode |

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight's minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

Constraints:

• m == dungeon.length
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

In simple terms, the question asks for the minimum initial health required for a knight to move from the top-left corner to the bottom-right corner, ensuring the health value is always greater than 0 at any point.

The function signature is as follows:

java 🟢

int calculateMinimumHP(int[][] grid);

cpp 🤖

int calculateMinimumHP(vector<vector<int>>& grid);

python 🤖

def calculateMinimumHP(grid: List[List[int]]) -> int:

go 🤖

func calculateMinimumHP(grid [][]int) int

javascript 🤖

var calculateMinimumHP = function(grid) {}

In the previous article Minimum Path Sum, we discussed a similar problem about finding the minimum path sum from the top-left corner to the bottom-right corner.

When solving algorithm problems, it's crucial to think creatively and apply what we've learned to new situations. Today's problem seems related to the minimum path sum, doesn't it?

To minimize the knight's initial health, does it mean we need to maximize the health potions along the knight's path? Is it equivalent to finding the "maximum path sum"? Can we directly apply the approach used for calculating the "minimum path sum"?

However, upon closer reflection, this reasoning doesn't hold. Consuming the most health potions doesn't necessarily guarantee the minimum initial health.

For example, in the following scenario, to get the most health potions and achieve the "maximum path sum," you should follow the path indicated by the arrows in the image below, requiring an initial health of 11:

But it's also evident that the correct path, as shown by the arrows in the image below, only requires an initial health of 1:

Therefore, the key is not to consume the most health potions, but to minimize the loss of health.

For these types of optimization problems, dynamic programming techniques are essential. We need to design the dp array/function definition appropriately. Analogous to the previous article Minimum Path Sum Problem, the dp function signature would look like this:

java 🟢

int dp(int[][] grid, int i, int j);

cpp 🤖

int dp(vector<vector<int>>& grid, int i, int j);

python 🤖

def dp(grid: List[List[int]], i: int, j: int) -> int:

go 🤖

func dp(grid [][]int, i int, j int) int {}

javascript 🤖

var dp = function(grid, i, j) {}

However, the definition of the dp function in this problem is quite interesting. Normally, the dp function should be defined as:

The minimum health required to move from the top-left corner (grid[0][0]) to grid[i][j] is dp(grid, i, j).

With this definition, the base case is when both i and j are 0. We can write the code as follows:

java 🟢

int calculateMinimumHP(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // We want to calculate the minimum health required from the top-left corner to the bottom-right corner
    return dp(grid, m - 1, n - 1);
}

int dp(int[][] grid, int i, int j) {
    // base case
    if (i == 0 && j == 0) {
        // Ensure the knight survives the landing
        return grid[i][j] > 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

cpp 🤖

int dp(vector<vector<int>>& grid, int i, int j) {
    // base case
    if (i == 0 && j == 0) {
        // ensure the knight survives upon landing
        return grid[i][j] > 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

int calculateMinimumHP(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    // we want to calculate the minimum health required from the top-left corner to the bottom-right corner
    return dp(grid, m - 1, n - 1);
}

python 🤖

def calculateMinimumHP(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    # we want to calculate the minimum health required from the top-left corner to the bottom-right corner
    return dp(grid, m - 1, n - 1)

def dp(grid: List[List[int]], i: int, j: int) -> int:
    # base case
    if i == 0 and j == 0:
        # ensure the knight survives upon landing
        return 1 if grid[i][j] > 0 else -grid[i][j] + 1
    ...

go 🤖

func calculateMinimumHP(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    // we want to calculate the minimum health value needed from the top-left corner to the bottom-right corner
    return dp(grid, m-1, n-1)
}

func dp(grid [][]int, i int, j int) int {
    // base case
    if i == 0 && j == 0 {
        // ensure the knight survives the landing
        if grid[i][j] > 0 {
            return 1
        } else {
            return -grid[i][j] + 1
        }
    }
    ...
}

javascript 🤖

var calculateMinimumHP = function(grid) {
    var m = grid.length;
    var n = grid[0].length;
    // We want to calculate the minimum health required from the top-left corner to the bottom-right corner
    return dp(grid, m - 1, n - 1);
}

var dp = function(grid, i, j) {
    // base case
    if (i == 0 && j == 0) {
        // Ensure the knight survives the landing
        return grid[i][j] > 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

注

For brevity, dp(grid, i, j) will be abbreviated as dp(i, j) from now on. Just understand the context.

Next, we need to find the state transition. Do you remember how to derive the state transition equation? Can our definition of the dp function correctly perform the state transition?

We hope that dp(i, j) can be derived from dp(i-1, j) and dp(i, j-1), so that we can continuously approach the base case and correctly perform the state transition.

Specifically, the "minimum health value to reach A" should be derived from the "minimum health value to reach B" and the "minimum health value to reach C":

But the question is, can it be derived? Actually, it cannot.

According to the definition of the dp function, you only know the "minimum health value to reach B from the top-left corner," but you do not know the "health value at B."

The "health value at B" is a necessary reference for state transition. Let me give you an example to illustrate. Suppose the following situation:

What do you think is the optimal route for the knight to rescue the princess in this case?

Obviously, it is to follow the blue line to B and then to A, right? This way, the initial health only needs to be 1. If you take the yellow arrow route, going to C first and then to A, the initial health needs to be at least 6.

Why is that? The minimum initial health for the knight to reach both B and C is 1. Why is the final route from B to A instead of from C to A?

Because when the knight reaches B, the health value is 11, while at C, the health value is still 1.

If the knight insists on going through C to A, the initial health must be increased to 6. But if going through B to A, an initial health of 1 is sufficient because the knight gains health from potions along the way, enough to withstand the damage from the monster at A.

This should be clear now. Revisiting our definition of the dp function, in the above situation, the algorithm only knows that dp(1, 2) = dp(2, 1) = 1, which are the same. How can it make the correct decision and calculate dp(2, 2)?

Therefore, our previous definition of the dp array was incorrect, lacking sufficient information for the algorithm to make the correct state transition.

The correct approach requires reverse thinking, still using the following dp function:

java 🟢

int dp(int[][] grid, int i, int j);

cpp 🤖

int dp(vector<vector<int>>& grid, int i, int j);

python 🤖

def dp(grid: List[List[int]], i: int, j: int) -> int:

go 🤖

func dp(grid [][]int, i int, j int) int {}

javascript 🤖

var dp = function(grid, i, j) {
  // function body here
};

However, we need to modify the definition of the dp function:

The minimum health required to reach the destination (bottom-right corner) from grid[i][j] is dp(grid, i, j).

You can write the code like this:

java 🟢

int calculateMinimumHP(int[][] grid) {
    // We want to calculate the minimum health value required from the top-left corner to the bottom-right corner
    return dp(grid, 0, 0);
}

int dp(int[][] grid, int i, int j) {
    int m = grid.length;
    int n = grid[0].length;
    // base case
    if (i == m - 1 && j == n - 1) {
        return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

cpp 🤖

int calculateMinimumHP(vector<vector<int>>& grid) {
    // We want to calculate the minimum health required from the top-left corner to the bottom-right corner
    return dp(grid, 0, 0);
}

int dp(vector<vector<int>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    // base case
    if (i == m - 1 && j == n - 1) {
        return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

python 🤖

def calculateMinimumHP(grid: List[List[int]]) -> int:
    # we want to calculate the minimum health value needed from the top-left corner to the bottom-right corner
    return dp(grid, 0, 0)

def dp(grid: List[List[int]], i: int, j: int) -> int:
    m = len(grid)
    n = len(grid[0])
    # base case
    if i == m - 1 and j == n - 1:
        return 1 if grid[i][j] >= 0 else -grid[i][j] + 1
    ...

go 🤖

func calculateMinimumHP(grid [][]int) int {
    // We want to calculate the minimum health value required from the top-left corner to the bottom-right corner
    return dp(grid, 0, 0)
}

func dp(grid [][]int, i int, j int) int {
    m := len(grid)
    n := len(grid[0])
    // base case
    if i == m-1 && j == n-1 {
        if grid[i][j] >= 0 {
            return 1
        } else {
            return -grid[i][j] + 1
        }
    }
    ...
}

javascript 🤖

// We want to calculate the minimum health required from the top-left corner to the bottom-right corner
var calculateMinimumHP = function(grid) {
    return dp(grid, 0, 0);
}

var dp = function(grid, i, j) {
    var m = grid.length;
    var n = grid[0].length;
    // base case
    if (i == m - 1 && j == n - 1) {
        return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
    }
    ...
}

Based on the new dp function definition and base case, we want to find dp(0, 0). To do this, we should try to derive dp(i, j) from dp(i, j+1) and dp(i+1, j), so we can gradually approach the base case and correctly perform state transitions.

Specifically, the "minimum health required to reach the bottom-right corner from A" should be derived from the "minimum health required to reach the bottom-right corner from B" and the "minimum health required to reach the bottom-right corner from C":

Can we derive it? This time, yes. Suppose dp(0, 1) = 5 and dp(1, 0) = 4. Then, it's clear that we should move from A to C because 4 is less than 5.

So, how do we determine the value of dp(0, 0)?

Assume the value at A is 1. Knowing that the next step is to move to C and dp(1, 0) = 4 means that at least 4 health points are needed to reach grid[1][0]. Therefore, we can determine that the knight needs 4 - 1 = 3 initial health points at A, right?

If the value at A is 10, the knight finds a large health potion immediately, exceeding the subsequent needs. 4 - 10 = -6 would mean the knight's initial health is negative, which is not possible. The knight dies if their health is less than 1, so in this case, the knight's initial health should be 1.

In summary, the state transition equation has been derived:

int res = min(
    dp(i + 1, j),
    dp(i, j + 1)
) - grid[i][j];

dp(i, j) = res <= 0 ? 1 : res;

根据这个核心逻辑，加一个备忘录消除重叠子问题，就可以直接写出最终的代码了：

java 🟢

class Solution {
    // main function
    public int calculateMinimumHP(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // initialize all values in the memo to -1
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dp(grid, 0, 0);
    }

    // memoization to eliminate overlapping subproblems
    int[][] memo;

    // definition: the minimum initial health required to reach the bottom-right corner from (i, j)
    int dp(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        // base case
        if (i == m - 1 && j == n - 1) {
            return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
        }
        if (i == m || j == n) {
            return Integer.MAX_VALUE;
        }
        // avoid repeated calculations
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // state transition logic
        int res = Math.min(
                dp(grid, i, j + 1),
                dp(grid, i + 1, j)
            ) - grid[i][j];
        // the knight's health must be at least 1
        memo[i][j] = res <= 0 ? 1 : res;

        return memo[i][j];
    }
}

cpp 🤖

class Solution {
public:
    // main function
    int calculateMinimumHP(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        // initialize all values in the memo to -1
        memo = vector<vector<int>>(m, vector<int>(n, -1));

        return dp(grid, 0, 0);
    }

private:
    // memoization to eliminate overlapping subproblems
    vector<vector<int>> memo;

    // definition: the minimum initial health required to reach the bottom-right corner from (i, j)
    int dp(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size();
        int n = grid[0].size();
        // base case
        if (i == m - 1 && j == n - 1) {
            return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
        }
        if (i == m || j == n) {
            return INT_MAX;
        }
        // avoid repeated calculations
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // state transition logic
        int res = min(
                dp(grid, i, j + 1),
                dp(grid, i + 1, j)
            ) - grid[i][j];
        // the knight's health must be at least 1
        memo[i][j] = res <= 0 ? 1 : res;

        return memo[i][j];
    }
};

python 🤖

class Solution:

    # main function
    def calculateMinimumHP(self, grid):
        m = len(grid)
        n = len(grid[0])
        # initialize all values in the memoization table to -1
        self.memo = [[-1]*n for _ in range(m)]

        return self.dp(grid, 0, 0)

    # definition: the minimum initial health required to reach the bottom-right corner from (i, j)
    def dp(self, grid, i, j):
        m = len(grid)
        n = len(grid[0])
        # base case
        if i == m - 1 and j == n - 1:
            return 1 if grid[i][j]>= 0 else -grid[i][j] + 1
        
        elif i == m or j == n:
            return float('inf')
        # avoid repeated calculations
        elif self.memo[i][j] != -1:
            return self.memo[i][j]
        # state transition logic
        else:
            res = min(
                self.dp(grid, i, j + 1),
                self.dp(grid, i + 1, j)
                ) - grid[i][j]
            # the knight's health must be at least 1
            self.memo[i][j] = res if res > 0 else 1

        return self.memo[i][j]

go 🤖

func calculateMinimumHP(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    // Initialize all values in the memo to -1
    memo := make([][]int, m)
    for i := range memo {
        memo[i] = make([]int, n)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    return dp(grid, 0, 0, memo)
}

// Definition: The minimum initial health required to reach the bottom-right corner from (i, j)
func dp(grid [][]int, i, j int, memo [][]int) int {
    m := len(grid)
    n := len(grid[0])
    // base case
    if i == m - 1 && j == n - 1 {
        if grid[i][j] >= 0 {
            return 1
        } else {
            return -grid[i][j] + 1
        }
    }
    if i == m || j == n {
        return math.MaxInt32
    }
    // Avoid repeated calculations
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    // State transition logic
    res := min(
        dp(grid, i, j + 1, memo),
        dp(grid, i + 1, j, memo),
    ) - grid[i][j]
    // The knight's health value must be at least 1
    if res <= 0 {
        memo[i][j] = 1
    } else {
        memo[i][j] = res
    }

    return memo[i][j]
}

javascript 🤖

var calculateMinimumHP = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    // Initialize all values in the memo to -1
    const memo = new Array(m).fill(0).map(() => new Array(n).fill(-1));

    return dp(grid, 0, 0, memo);
}

// Definition: The minimum initial health required to reach the bottom-right corner from (i, j)
var dp = function(grid, i, j, memo) {
    const m = grid.length;
    const n = grid[0].length;
    // base case
    if (i == m - 1 && j == n - 1) {
        return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
    }
    if (i == m || j == n) {
        return Number.MAX_SAFE_INTEGER;
    }
    // Avoid repeated calculations
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    // State transition logic
    const res = Math.min(
        dp(grid, i, j + 1, memo),
        dp(grid, i + 1, j, memo)
    ) - grid[i][j];
    // The knight's health must be at least 1
    memo[i][j] = res <= 0 ? 1 : res;

    return memo[i][j];
}

This is the top-down dynamic programming solution with memoization. Referencing the previous article Dynamic Programming Techniques Explained, it can be easily rewritten as an iterative solution using a dp array. I won't write it out here, but readers are encouraged to try it themselves.

The core of this problem is to define the dp function, find the correct state transition equation, and thereby calculate the correct answer.