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

Info

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

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

LeetCode | Difficulty |
---|---|

174. Dungeon Game | 🔴 |

"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:7Explanation: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:

`int calculateMinimumHP(int[][] grid);`

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

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

`func calculateMinimumHP(grid [][]int) int`

`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:

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

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

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

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

`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:

```
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;
}
...
}
```

```
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);
}
```

```
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
...
```

```
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
}
}
...
}
```

```
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:

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

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

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

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

```
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:

```
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;
}
...
}
```

```
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;
}
...
}
```

```
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
...
```

```
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
}
}
...
}
```

```
// 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;
```

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

```
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];
}
}
```

```
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];
}
};
```

```
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]
```

```
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]
}
```

```
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.