Play Dungeon Game with DP

"The Magic Tower" is a classic dungeon crawler game where you lose health when encountering monsters, gain health by consuming health potions, collect keys, and advance through levels to ultimately rescue the beautiful princess.

This game is still available on mobile devices today:

Many people probably have fond childhood memories of this game. I remember playing it alone on a gaming device, surrounded by two or three friends giving directions, which made the gaming experience quite frustrating for the player but extremely enjoyable 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

The problem is from LeetCode 174. Dungeon Game.

In simple terms, it asks how much initial health is needed for a knight to move from the top-left corner to the bottom-right corner, ensuring 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 corner to the bottom-right corner.

When solving algorithm problems, we should always try to draw inferences from one instance to another. It feels like today's problem is somewhat related to the minimum path sum, right?

Minimizing the knight's initial health means maximizing the health potions along the knight's path. Isn't it equivalent to finding the "maximum path sum"? Can we directly apply the thought process of calculating the "minimum path sum"?

However, after some thought, this inference does not hold; collecting the most health potions does not necessarily result in the minimum initial health.

For example, in the following case, if you want to collect the most potions for the "maximum path sum," you should follow the path shown by the arrows in the image below, requiring an initial health of 11:

But it's easy to see that the correct path is shown by the arrows in the image below, requiring only an initial health of 1:

So, the key is not in collecting the most potions but in losing the least health.

For such optimization problems, dynamic programming techniques must be used, and the dp array/function definition must be designed appropriately. Referring to the previous article Minimum Path Sum Problem, the dp function signature will likely be 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) {}

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

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

With this definition, the base case occurs when both i and j equal 0, and 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 simplicity, we will abbreviate dp(grid, i, j) as dp(i, j) from now on, and you should understand the context.

Next, we need to find the state transition. Do you remember how to derive the state transition equation? Can we correctly perform state transitions with this 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 progressively approach the base case and ensure correct state transitions.

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

But the problem is, can we derive it? In fact, 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 level when reaching B."

The "health level when reaching B" is a necessary reference for state transitions. Let me give you an example:

What do you think is the optimal path for the knight to rescue the princess in this scenario?

Clearly, it's to follow the blue line to B and then to A, right? This way, the initial health required is only 1. If you follow the yellow arrow path, first going to C and then to A, the initial health required would be at least 6.

Why is this the case? The minimum initial health to reach both B and C is 1. Why is the path from B to A preferred over C to A?

Because when the knight reaches B, the health level is 11, but when reaching C, it remains 1.

If the knight insists on going from C to A, the initial health must be increased to 6; but if from B to A, an initial health of 1 is sufficient because health potions picked up along the way provide enough health to withstand the damage from monsters above A.

This should be clear now. Reviewing our definition of the dp function, in the above scenario, the algorithm only knows that dp(1, 2) = dp(2, 1) = 1, which is the same. How can it make the right decision and compute dp(2, 2)?

Therefore, our previous definition of the dp array was incorrect; it lacked 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) {}

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

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

The code can be written as follows:

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 definition of the dp function and the base case, we aim to solve for dp(0, 0). We should try to derive dp(i, j) from dp(i, j+1) and dp(i+1, j) to gradually approach the base case and correctly perform state transitions.

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

Can it be derived? Yes, it can. Suppose dp(0, 1) = 5 and dp(1, 0) = 4, then it is certain to move from A to C since 4 is less than 5.

How can we determine what dp(0, 0) should be?

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

If the value of A is 10, and it provides a large health boost, exceeding subsequent requirements, 4 - 10 = -6 implies that the knight's initial health would be negative, which is not possible. The knight's health cannot be less than 1, so in this case, the initial health should be 1.

In conclusion, the state transition equation is derived as follows:

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

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

With this core logic, adding a memoization to eliminate overlapping subproblems allows us to write the final code directly:

class Solution {

    public int calculateMinimumHP(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // initialize the memo array with -1
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dp(grid, 0, 0);
    }

    // memo array 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 redundant 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];
        // knight's health must be at least 1
        memo[i][j] = res <= 0 ? 1 : res;

        return memo[i][j];
    }
}

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {

public:
    int calculateMinimumHP(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        // initialize the memo array with -1
        memo = vector<vector<int>>(m, vector<int>(n, -1));

        return dp(grid, 0, 0);
    }

private:
    // memo array 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 redundant 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];
        // knight's health must be at least 1
        memo[i][j] = res <= 0 ? 1 : res;

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

class Solution:

    def calculateMinimumHP(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # initialize the memo array with -1
        self.memo = [[-1] * n for _ in range(m)]

        return self.dp(grid, 0, 0)

    # memo array to eliminate overlapping subproblems
    memo = []

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

        return self.memo[i][j]

import (
	"math"
)

func calculateMinimumHP(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	// initialize the memo array with -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)
}

// memo array to eliminate overlapping subproblems
// 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
		}
		return -grid[i][j] + 1
	}
	if i >= m || j >= n {
		// Out of bounds, return a large number that represents impossible to proceed
		return math.MaxInt32
	}
	// avoid redundant calculations
	if memo[i][j] != -1 {
		return memo[i][j]
	}
	// state transition logic
	right := dp(grid, i, j+1, memo)
	down := dp(grid, i+1, j, memo)
	res := int(math.Min(float64(right), float64(down))) - grid[i][j]
	// knight's health must be at least 1
	memo[i][j] = max(res, 1)

	return memo[i][j]
}

// Helper function to return the maximum of two integers.
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var calculateMinimumHP = function(grid) {
    let m = grid.length;
    let n = grid[0].length;
    // initialize the memo array with -1
    let memo = Array.from({ length: m }, () => Array(n).fill(-1));

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

// memo array to eliminate overlapping subproblems
// definition: the minimum initial health required to reach the bottom-right corner from (i, j)
// @visualize status(i,j)
var dp = function(grid, i, j, memo) {
    let m = grid.length;
    let 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 redundant calculations
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    // state transition logic
    let res = Math.min(
        dp(grid, i, j + 1, memo),
        dp(grid, i + 1, j, memo)
    ) - grid[i][j];
    // 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. Referring to the previous article Dynamic Programming Detailed Explanation, it can be easily rewritten as an iterative solution using a dp array, which is not included here. Readers can try writing it themselves.

The key to this problem is defining the dp function, finding the correct state transition equation, and thus calculating the correct answer.