Play Dungeon Game with DP

"The Magic Tower" is a classic dungeon game where encountering monsters reduces your health, consuming health potions increases it, and you need to collect keys to move up levels and eventually rescue the beautiful princess.

This game is still playable on mobile phones today:

Indeed, this game holds many childhood memories. Remember playing it alone with a console, while two or three people stood around giving unsolicited advice, making the experience terrible for the player but extremely fun for the onlookers 😂

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

Simply put, it asks you how much minimum initial health is needed for the knight to move from the top-left corner to the bottom-right corner, ensuring his health 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) {}

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 determine the state transition. Do you remember how to find the state transition equation? Can our definition of the dp function correctly perform state transitions?

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 state transitions.

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

However, the question is, can it be derived? In reality, 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 upon arrival."

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

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

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 follow the yellow arrow route, going to C first and then to A, the initial health would need to be at least 6.

Why is this the case? The minimum initial health required 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, whereas at C, the health value remains 1.

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

This should make it very clear. Revisiting our definition of the dp function, in the scenario above, 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 correct state transitions.

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