Dungeon Game

Problem

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.

Examples

Example 1:

1
2
3
4
5


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.

Basically our Knight is at 0,0 and princes at n-1, n-1:

Constraints

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

Solution

Here we have been given a matrix we need to start from top and find a way to get to bottom right, we need the min cost that is required to do this. We can only go down or right. Also:

At any point if Knight’s health gets zero of below we dies, so : we need 1 + (- min cost) for our health to be one.
What if we get some health if we arrive at some cell ? my guess is we still need 1 health in first case to arrive at that cell - cases like these need to be figure out by yourself.
at any cell what health do we need ? - since we can go only down and right therefore min health required will be minimun health required if we go right or down, ( futher explained in arriving at recurrance relation heading )

Method 1 - Binary Search

Intuition

Use binary search to find the minimum initial health required. For each candidate health, use DFS to check if the knight can reach the princess without dying. Adjust the search bounds based on feasibility.

Approach

Set the search bounds based on the worst-case negative sum. For each mid value, use DFS to check if a path exists with that initial health. If yes, try a smaller value; otherwise, try a larger one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
	bool dfs(int health, int r, int c, const vector<vector<int>>& dungeon) {
		int m = dungeon.size(), n = dungeon[0].size();
		if (r >= m || c >= n || health <= 0) return false;
		if (r == m - 1 && c == n - 1) return health + dungeon[r][c] > 0;
		int nextHealth = health + dungeon[r][c];
		return dfs(nextHealth, r + 1, c, dungeon) || dfs(nextHealth, r, c + 1, dungeon);
	}
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		int left = 1, right = 200001;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (dfs(mid, 0, 0, dungeon)) right = mid;
			else left = mid + 1;
		}
		return left;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func calculateMinimumHP(dungeon [][]int) int {
	m, n := len(dungeon), len(dungeon[0])
	var dfs func(health, r, c int) bool
	dfs = func(health, r, c int) bool {
		if r >= m || c >= n || health <= 0 {
			return false
		}
		if r == m-1 && c == n-1 {
			return health+dungeon[r][c] > 0
		}
		next := health + dungeon[r][c]
		return dfs(next, r+1, c) || dfs(next, r, c+1)
	}
	left, right := 1, 200001
	for left < right {
		mid := left + (right-left)/2
		if dfs(mid, 0, 0) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public int calculateMinimumHP(int[][] dungeon) {
	int left = 1, right = 200001;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (dfs(mid, 0, 0, dungeon)) right = mid;
		else left = mid + 1;
	}
	return left;
}
private boolean dfs(int health, int r, int c, int[][] dungeon) {
	int m = dungeon.length, n = dungeon[0].length;
	if (r >= m || c >= n || health <= 0) return false;
	if (r == m - 1 && c == n - 1) return health + dungeon[r][c] > 0;
	int next = health + dungeon[r][c];
	return dfs(next, r + 1, c, dungeon) || dfs(next, r, c + 1, dungeon);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
	fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
		val m = dungeon.size
		val n = dungeon[0].size
		fun dfs(health: Int, r: Int, c: Int): Boolean {
			if (r >= m || c >= n || health <= 0) return false
			if (r == m - 1 && c == n - 1) return health + dungeon[r][c] > 0
			val next = health + dungeon[r][c]
			return dfs(next, r + 1, c) || dfs(next, r, c + 1)
		}
		var left = 1
		var right = 200001
		while (left < right) {
			val mid = left + (right - left) / 2
			if (dfs(mid, 0, 0)) right = mid
			else left = mid + 1
		}
		return left
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
	def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
		m, n = len(dungeon), len(dungeon[0])
		def dfs(health, r, c):
			if r >= m or c >= n or health <= 0:
				return False
			if r == m - 1 and c == n - 1:
				return health + dungeon[r][c] > 0
			next_health = health + dungeon[r][c]
			return dfs(next_health, r + 1, c) or dfs(next_health, r, c + 1)
		left, right = 1, 200001
		while left < right:
			mid = (left + right) // 2
			if dfs(mid, 0, 0):
				right = mid
			else:
				left = mid + 1
		return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
	pub fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
		fn dfs(health: i32, r: usize, c: usize, dungeon: &Vec<Vec<i32>>) -> bool {
			let m = dungeon.len();
			let n = dungeon[0].len();
			if r >= m || c >= n || health <= 0 { return false; }
			if r == m - 1 && c == n - 1 { return health + dungeon[r][c] > 0; }
			let next = health + dungeon[r][c];
			dfs(next, r + 1, c, dungeon) || dfs(next, r, c + 1, dungeon)
		}
		let (mut left, mut right) = (1, 200001);
		while left < right {
			let mid = left + (right - left) / 2;
			if dfs(mid, 0, 0, &dungeon) { right = mid; }
			else { left = mid + 1; }
		}
		left
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function calculateMinimumHP(dungeon: number[][]): number {
	const m = dungeon.length, n = dungeon[0].length;
	function dfs(health: number, r: number, c: number): boolean {
		if (r >= m || c >= n || health <= 0) return false;
		if (r === m - 1 && c === n - 1) return health + dungeon[r][c] > 0;
		const next = health + dungeon[r][c];
		return dfs(next, r + 1, c) || dfs(next, r, c + 1);
	}
	let left = 1, right = 200001;
	while (left < right) {
		const mid = Math.floor((left + right) / 2);
		if (dfs(mid, 0, 0)) right = mid;
		else left = mid + 1;
	}
	return left;
}

Complexity

⏰ Time complexity: O((m+n) * log(maxSum)) in practice, but can be exponential due to DFS (not efficient for large grids).
🧺 Space complexity: O(m+n) for recursion stack.

Method 2 - Recursion

Intuition

Use recursion to explore all possible paths from the top-left to the bottom-right cell. At each cell, calculate the minimum health required to reach the princess, considering both right and down moves.

Approach

Define a recursive function that, for each cell, returns the minimum health required to reach the princess. The base case is reaching the princess’s cell, where the required health depends on the cell value. For other cells, take the minimum of the right and down moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
	int dfs(int i, int j, const vector<vector<int>>& dungeon) {
		int m = dungeon.size(), n = dungeon[0].size();
		if (i >= m || j >= n) return INT_MAX;
		if (i == m - 1 && j == n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
		int right = dfs(i, j + 1, dungeon);
		int down = dfs(i + 1, j, dungeon);
		int need = min(right, down) - dungeon[i][j];
		return max(need, 1);
	}
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		return dfs(0, 0, dungeon);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func calculateMinimumHP(dungeon [][]int) int {
	m, n := len(dungeon), len(dungeon[0])
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m || j >= n {
			return 1 << 30
		}
		if i == m-1 && j == n-1 {
			if dungeon[i][j] >= 0 {
				return 1
			}
			return 1 - dungeon[i][j]
		}
		right := dfs(i, j+1)
		down := dfs(i+1, j)
		need := min(right, down) - dungeon[i][j]
		if need < 1 {
			need = 1
		}
		return need
	}
	return dfs(0, 0)
}
func min(a, b int) int { if a < b { return a }; return b }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public int calculateMinimumHP(int[][] dungeon) {
	return dfs(0, 0, dungeon);
}
private int dfs(int i, int j, int[][] dungeon) {
	int m = dungeon.length, n = dungeon[0].length;
	if (i >= m || j >= n) return Integer.MAX_VALUE;
	if (i == m - 1 && j == n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
	int right = dfs(i, j + 1, dungeon);
	int down = dfs(i + 1, j, dungeon);
	int need = Math.min(right, down) - dungeon[i][j];
	return Math.max(need, 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
	fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
		val m = dungeon.size
		val n = dungeon[0].size
		fun dfs(i: Int, j: Int): Int {
			if (i >= m || j >= n) return Int.MAX_VALUE
			if (i == m - 1 && j == n - 1) return if (dungeon[i][j] >= 0) 1 else 1 - dungeon[i][j]
			val right = dfs(i, j + 1)
			val down = dfs(i + 1, j)
			val need = minOf(right, down) - dungeon[i][j]

Intuition

Recursively explore all possible paths from the top-left to the bottom-right cell. At each cell, calculate the minimum health required to reach the princess, considering both right and down moves.

Approach

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
	int dfs(int i, int j, const vector<vector<int>>& dungeon) {
		int m = dungeon.size(), n = dungeon[0].size();
		if (i >= m || j >= n) return INT_MAX;
		if (i == m - 1 && j == n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
		int right = dfs(i, j + 1, dungeon);
		int down = dfs(i + 1, j, dungeon);
		int need = min(right, down) - dungeon[i][j];
		return max(need, 1);
	}
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		return dfs(0, 0, dungeon);
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func calculateMinimumHP(dungeon [][]int) int {
	m, n := len(dungeon), len(dungeon[0])
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i >= m || j >= n {
			return 1 << 30
		}
		if i == m-1 && j == n-1 {
			if dungeon[i][j] >= 0 {
				return 1
			}
			return 1 - dungeon[i][j]
		}
		right := dfs(i, j+1)
		down := dfs(i+1, j)
		need := min(right, down) - dungeon[i][j]
		if need < 1 {
			need = 1
		}
		return need
	}
	return dfs(0, 0)
}
func min(a, b int) int { if a < b { return a }; return b }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public int calculateMinimumHP(int[][] dungeon) {
	return dfs(0, 0, dungeon);
}
private int dfs(int i, int j, int[][] dungeon) {
	int m = dungeon.length, n = dungeon[0].length;
	if (i >= m || j >= n) return Integer.MAX_VALUE;
	if (i == m - 1 && j == n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
	int right = dfs(i, j + 1, dungeon);
	int down = dfs(i + 1, j, dungeon);
	int need = Math.min(right, down) - dungeon[i][j];
	return Math.max(need, 1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
	fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
		val m = dungeon.size
		val n = dungeon[0].size
		fun dfs(i: Int, j: Int): Int {
			if (i >= m || j >= n) return Int.MAX_VALUE
			if (i == m - 1 && j == n - 1) return if (dungeon[i][j] >= 0) 1 else 1 - dungeon[i][j]
			val right = dfs(i, j + 1)
			val down = dfs(i + 1, j)
			val need = minOf(right, down) - dungeon[i][j]
			return maxOf(need, 1)
		}
		return dfs(0, 0)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
	def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
		m, n = len(dungeon), len(dungeon[0])
		def dfs(i, j):
			if i >= m or j >= n:
				return float('inf')
			if i == m - 1 and j == n - 1:
				return 1 if dungeon[i][j] >= 0 else 1 - dungeon[i][j]
			right = dfs(i, j + 1)
			down = dfs(i + 1, j)
			need = min(right, down) - dungeon[i][j]
			return max(need, 1)
		return dfs(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


impl Solution {
	pub fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
		fn dfs(i: usize, j: usize, dungeon: &Vec<Vec<i32>>) -> i32 {
			let m = dungeon.len();
			let n = dungeon[0].len();
			if i >= m || j >= n { return i32::MAX; }
			if i == m - 1 && j == n - 1 {
				return if dungeon[i][j] >= 0 { 1 } else { 1 - dungeon[i][j] };
			}
			let right = dfs(i, j + 1, dungeon);
			let down = dfs(i + 1, j, dungeon);
			let need = right.min(down) - dungeon[i][j];
			need.max(1)
		}
		dfs(0, 0, &dungeon)
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


function calculateMinimumHP(dungeon: number[][]): number {
	const m = dungeon.length, n = dungeon[0].length;
	function dfs(i: number, j: number): number {
		if (i >= m || j >= n) return Number.POSITIVE_INFINITY;
		if (i === m - 1 && j === n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
		const right = dfs(i, j + 1);
		const down = dfs(i + 1, j);
		const need = Math.min(right, down) - dungeon[i][j];
		return Math.max(need, 1);
	}
	return dfs(0, 0);
}

Complexity

⏰ Time complexity: O(2^(m+n)), where m and n are the dimensions of the dungeon. Each cell can branch to two paths.
🧺 Space complexity: O(m+n), for the recursion stack. int[][] memo = new int[m][n]; for (int[] row : memo) Arrays.fill(row, -1); return dfs(0, 0, dungeon, memo); } private int dfs(int i, int j, int[][] dungeon, int[][] memo) { int m = dungeon.length, n = dungeon[0].length; if (i >= m || j >= n) return Integer.MAX_VALUE; if (memo[i][j] != -1) return memo[i][j]; if (i == m - 1 && j == n - 1) return dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j]; int right = dfs(i, j + 1, dungeon, memo); int down = dfs(i + 1, j, dungeon, memo); int need = Math.min(right, down) - dungeon[i][j]; memo[i][j] = Math.max(need, 1); return memo[i][j]; }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22



##### Kotlin

```kotlin
class Solution {
	fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
		val m = dungeon.size
		val n = dungeon[0].size
		val memo = Array(m) { IntArray(n) { -1 } }
		fun dfs(i: Int, j: Int): Int {
			if (i >= m || j >= n) return Int.MAX_VALUE
			if (memo[i][j] != -1) return memo[i][j]
			if (i == m - 1 && j == n - 1) return if (dungeon[i][j] >= 0) 1 else 1 - dungeon[i][j]
			val right = dfs(i, j + 1)
			val down = dfs(i + 1, j)
			val need = minOf(right, down) - dungeon[i][j]
			memo[i][j] = maxOf(need, 1)
			return memo[i][j]
		}
		return dfs(0, 0)
	}
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
	def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
		m, n = len(dungeon), len(dungeon[0])
		memo = [[-1] * n for _ in range(m)]
		def dfs(i, j):
			if i >= m or j >= n:
				return float('inf')
			if memo[i][j] != -1:
				return memo[i][j]
			if i == m - 1 and j == n - 1:
				memo[i][j] = 1 if dungeon[i][j] >= 0 else 1 - dungeon[i][j]
				return memo[i][j]
			right = dfs(i, j + 1)
			down = dfs(i + 1, j)
			need = min(right, down) - dungeon[i][j]
			memo[i][j] = max(need, 1)
			return memo[i][j]
		return dfs(0, 0)

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
	pub fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
		fn dfs(i: usize, j: usize, dungeon: &Vec<Vec<i32>>, memo: &mut Vec<Vec<i32>>) -> i32 {
			let m = dungeon.len();
			let n = dungeon[0].len();
			if i >= m || j >= n { return i32::MAX; }
			if memo[i][j] != -1 { return memo[i][j]; }
			if i == m - 1 && j == n - 1 {
				memo[i][j] = if dungeon[i][j] >= 0 { 1 } else { 1 - dungeon[i][j] };
				return memo[i][j];
			}
			let right = dfs(i, j + 1, dungeon, memo);
			let down = dfs(i + 1, j, dungeon, memo);
			let need = right.min(down) - dungeon[i][j];
			memo[i][j] = need.max(1);
			memo[i][j]
		}
		let m = dungeon.len();
		let n = dungeon[0].len();
		let mut memo = vec![vec![-1; n]; m];
		dfs(0, 0, &dungeon, &mut memo)
	}
}

TypeScript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


function calculateMinimumHP(dungeon: number[][]): number {
	const m = dungeon.length, n = dungeon[0].length;
	const memo: number[][] = Array.from({ length: m }, () => Array(n).fill(-1));
	function dfs(i: number, j: number): number {
		if (i >= m || j >= n) return Number.POSITIVE_INFINITY;
		if (memo[i][j] !== -1) return memo[i][j];
		if (i === m - 1 && j === n - 1) {
			memo[i][j] = dungeon[i][j] >= 0 ? 1 : 1 - dungeon[i][j];
			return memo[i][j];
		}
		const right = dfs(i, j + 1);
		const down = dfs(i + 1, j);
		const need = Math.min(right, down) - dungeon[i][j];
		memo[i][j] = Math.max(need, 1);
		return memo[i][j];
	}
	return dfs(0, 0);
}

Complexity

⏰ Time complexity: O(mn), where m and n are the dimensions of the dungeon. Each cell is computed once.
🧺 Space complexity: O(mn), for the memoization table.

This problem can be solved by using dynamic programming. We maintain a 2-D table. h[i][j] is the minimum health value before he enters (i, j). h[0][0] is the value of the answer. The left part is filling in numbers to the table.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


public int calculateMinimumHP(int[][] dungeon) {
	int m = dungeon.length;
	int n = dungeon[0].length;

	//init dp table
	int[][] h = new int[m][n];

	h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);

	//init last row
	for (int i = m - 2; i >= 0; i--) {
		h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
	}

	//init last column
	for (int j = n - 2; j >= 0; j--) {
		h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
	}

	//calculate dp table
	for (int i = m - 2; i >= 0; i--) {
		for (int j = n - 2; j >= 0; j--) {
			int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);
			int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);
			h[i][j] = Math.min(right, down);
		}
	}

	return h[0][0];
}

Method 4 - Bottom up DP

Intuition

Start from the princess’s cell and work backwards to the knight’s starting cell. At each cell, compute the minimum health required to move right or down, ensuring the knight never dies.

Approach

Create a DP table where dp[i][j] is the minimum health required to enter cell (i, j). Fill the table from the bottom-right to the top-left, using the recurrence relation based on right and down moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		int m = dungeon.size(), n = dungeon[0].size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
		dp[m][n - 1] = dp[m - 1][n] = 1;
		for (int i = m - 1; i >= 0; --i) {
			for (int j = n - 1; j >= 0; --j) {
				int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
				dp[i][j] = max(need, 1);
			}
		}
		return dp[0][0];
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func calculateMinimumHP(dungeon [][]int) int {
	m, n := len(dungeon), len(dungeon[0])
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		for j := range dp[i] {
			dp[i][j] = 1 << 30
		}
	}
	dp[m][n-1], dp[m-1][n] = 1, 1
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			need := min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
			if need < 1 {
				need = 1
			}
			dp[i][j] = need
		}
	}
	return dp[0][0]
}
func min(a, b int) int { if a < b { return a }; return b }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public int calculateMinimumHP(int[][] dungeon) {
	int m = dungeon.length, n = dungeon[0].length;
	int[][] dp = new int[m + 1][n + 1];
	for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
	dp[m][n - 1] = dp[m - 1][n] = 1;
	for (int i = m - 1; i >= 0; i--) {
		for (int j = n - 1; j >= 0; j--) {
			int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
			dp[i][j] = Math.max(need, 1);
		}
	}
	return dp[0][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
		val m = dungeon.size
		val n = dungeon[0].size
		val dp = Array(m + 1) { IntArray(n + 1) { Int.MAX_VALUE } }
		dp[m][n - 1] = 1
		dp[m - 1][n] = 1
		for (i in m - 1 downTo 0) {
			for (j in n - 1 downTo 0) {
				val need = minOf(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
				dp[i][j] = maxOf(need, 1)
			}
		}
		return dp[0][0]
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
	def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
		m, n = len(dungeon), len(dungeon[0])
		dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
		dp[m][n - 1] = dp[m - 1][n] = 1
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
				dp[i][j] = max(need, 1)
		return dp[0][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
	pub fn calculate_minimum_hp(dungeon: Vec<Vec<i32>>) -> i32 {
		let m = dungeon.len();
		let n = dungeon[0].len();
		let mut dp = vec![vec![i32::MAX; n + 1]; m + 1];
		dp[m][n - 1] = 1;
		dp[m - 1][n] = 1;
		for i in (0..m).rev() {
			for j in (0..n).rev() {
				let need = dp[i + 1][j].min(dp[i][j + 1]) - dungeon[i][j];
				dp[i][j] = need.max(1);
			}
		}
		dp[0][0]
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


function calculateMinimumHP(dungeon: number[][]): number {
	const m = dungeon.length, n = dungeon[0].length;
	const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(Infinity));
	dp[m][n - 1] = 1;
	dp[m - 1][n] = 1;
	for (let i = m - 1; i >= 0; i--) {
		for (let j = n - 1; j >= 0; j--) {
			const need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
			dp[i][j] = Math.max(need, 1);
		}
	}
	return dp[0][0];
}

Complexity

⏰ Time complexity: O(mn), where m and n are the dimensions of the dungeon. Each cell is computed once.
🧺 Space complexity: O(mn), for the DP table.

Problem#

Examples#

Constraints#

Solution#

Method 1 - Binary Search#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Recursion#

Intuition#

Approach#

Code#

Intuition#

Approach#

Code#

Complexity#

Python#

Rust#

TypeScript#

Complexity#

Method 4 - Bottom up DP#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Constraints

Solution

Method 1 - Binary Search

Intuition

Approach

Code

Complexity

Method 2 - Recursion

Intuition

Approach

Code

Intuition

Approach

Code

Complexity

Python

Rust

TypeScript

Complexity

Method 4 - Bottom up DP

Intuition

Approach

Code

Complexity