Play Dungeon Game with DP

"Magic Tower" is a classic dungeon game where you lose health upon encountering monsters and gain health by consuming health potions. You need to collect keys to ascend each level, ultimately rescuing the beautiful princess.

You can still play this game on mobile devices today:

Indeed, this game brings back childhood memories for many. I remember playing alone with a handheld console while two or three others crowded around, suggesting moves, which made the gaming experience quite poor for the player but exceptionally fun for the onlookers 😂

LeetCode Problem 174, "Dungeon Game," presents 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, it asks how much minimum initial health is required for the knight to move from the top-left corner to the bottom-right corner while ensuring that the health is always greater than 0.

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) {}

The previous article Minimum Path Sum discussed a similar problem, asking for the minimum path sum from the top-left to the bottom-right corner.

When solving algorithm problems, we should always try to draw parallels. Today’s problem seems related to the minimum path sum, doesn't it?

To minimize the knight's initial health points, does it mean maximizing the health potions along the knight's path? Is it like finding the "maximum path sum"? Can we directly apply the approach for calculating the "minimum path sum"?

However, with some thought, this inference does not hold. Consuming the maximum number of health potions does not necessarily lead to the minimum initial health points.

For example, in the situation below, to consume the most health potions and achieve the "maximum path sum," the path should follow the arrows shown in the image. The initial health points required would be 11:

But it can be easily seen that the correct path follows the arrows shown in the image below, requiring only 1 initial health point:

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

For such problems that require finding an optimal value, dynamic programming techniques should be used, with a well-designed dp array/function definition. Similar to the previous Minimum Path Sum Problem, the dp function signature should 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
    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
    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
    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
    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
    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;
    }
    ...
}

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

We want dp(i, j) to be derived from dp(i-1, j) and dp(i, j-1), so that we can keep approaching the base case and perform the state transitions correctly.

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

But the problem is, can we derive it? In reality, we cannot.

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

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

In this scenario, what is the optimal route for the knight to rescue the princess?

Clearly, it is to follow the blue line to B, and then to A, as shown in the diagram. 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 this the case? The minimum initial health required to reach both B and C is 1, so why go from B to A instead of from C to A?

This is because when the knight reaches B, the health is 11, while when reaching C, the health remains 1.

If the knight insists on going through C to reach A, the initial health must be increased to 6. However, if the knight goes through B to reach A, an initial health of 1 is sufficient because the knight picks up a health potion on the way, providing enough health to withstand the damage from the monster at A.

This should be clear now. Reviewing our definition of the dp function, in this scenario, the algorithm only knows 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. It lacked information, and the algorithm couldn't make the correct state transition.

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

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
    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
    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
    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
    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, when we want to find dp(0, 0), we should attempt to derive dp(i, j) through dp(i, j+1) and dp(i+1, j). This approach allows us to gradually reach the base case and correctly perform state transitions.

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

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

How can we determine what dp(0, 0) is?

Assume the value of A is 1. Since the next step is towards C, and dp(1, 0) = 4 means that at least 4 health points are needed when reaching grid[1][0], we can conclude that the knight needs 4 - 1 = 3 initial health points at point A.

If A's value is 10, and a large health potion is picked up immediately, surpassing the subsequent requirement, 4 - 10 = -6 implies the knight's initial health would be negative, which is not possible. The knight's health cannot drop below 1, so in such cases, 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
    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
    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
    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.