Dungeon Game

🎯

Dungeon Game

hardDPAmazonGoogle

Imagine a knight trapped in a dungeon filled with monsters and magic potions, needing to find the minimum initial health to survive the journey to rescue the princess.

💡 This problem is a classic example of grid-based dynamic programming where the challenge is to minimize the initial health required to survive a path with both positive and negative effects. Beginners often struggle because the problem requires reasoning backwards from the destination to the start, which is counterintuitive compared to typical forward DP problems.

📋

Problem Statement

You are given an m x n grid dungeon where each cell contains an integer representing health points gained (positive) or lost (negative). The knight starts at the top-left cell and must reach the bottom-right cell by moving only right or down. The knight's health must never drop to zero or below at any point. Determine the minimum initial health the knight needs to start with to reach the princess safely.

1 ≤ m, n ≤ 200-1000 ≤ dungeon[i][j] ≤ 1000

💡

Example

Input"[[-2,-3,3],[-5,-10,1],[10,30,-5]]"

Output7

Starting with 7 health, the knight can survive the path (right, right, down, down) without health dropping below 1.

• Single cell with positive value → minimum initial health is 1
• Single cell with negative value → minimum initial health is 1 - cell value
• All cells zero → minimum initial health is 1
• Large grid with all negative values → initial health must cover worst path

🔁

Why DP?

Why greedy fails:

A greedy approach that tries to minimize health loss at each step fails because a locally optimal choice may lead to an impossible path later. For example, choosing a path with less immediate damage might lead to a cell with huge negative value that cannot be survived.

DP state:

dp[i][j] represents the minimum health the knight needs to have upon entering cell (i, j) to ensure survival until the princess is rescued.

Recurrence:dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

The minimum health needed at cell (i,j) is the minimum of the health needed in the cells to the right and below, minus the current cell's value, but at least 1 to survive.

⚠️

Common Mistakes

Not handling the base case correctly at the princess cell

Incorrect minimum health calculation leading to wrong answer

✅ Set dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]) explicitly

Using forward DP from start to end instead of backward from end to start

Cannot correctly compute minimum health needed because future states are unknown

✅ Fill dp table from bottom-right to top-left

Not ensuring minimum health is at least 1 at each cell

Health can drop to zero or below, violating problem constraints

✅ Use max(1, calculated_health) at each dp cell

Forgetting to initialize dp boundaries with infinity or max value

Boundary conditions cause incorrect minimum calculations

✅ Initialize dp[m][*] and dp[*][n] with infinity except dp[m][n-1] and dp[m-1][n] = 1

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated calculations.

Intuition

Try all possible paths from the start to the end, recursively calculating the minimum initial health needed for each path, and take the minimum over all paths.

Algorithm

1. Define a recursive function that returns the minimum health needed to survive from the current cell to the princess.
2. At each cell, recursively compute the minimum health needed for the right and down cells.
3. Calculate the minimum health needed at the current cell based on the minimum of the two recursive calls minus the current cell's value.
4. Return the maximum of 1 and the calculated health to ensure survival.

💡 The recursion is hard to visualize because it explores all paths and calculates health backwards, which is opposite to usual forward traversal.

Recurrence:dp(i,j) = max(1, min(dp(i+1,j), dp(i,j+1)) - dungeon[i][j])

</>

Code

from typing import List

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')  # Out of bounds means no path
            if i == m - 1 and j == n - 1:
                return max(1, 1 - dungeon[i][j])
            down = dfs(i + 1, j)
            right = dfs(i, j + 1)
            need = min(down, right) - dungeon[i][j]
            return max(1, need)

        return dfs(0, 0)

# Example usage:
# sol = Solution()
# print(sol.calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]]))  # Output: 7

Line Notes

def dfs(i, j):Defines the recursive function to compute minimum health from cell (i,j)

if i == m or j == n:Checks for out-of-bounds, returns infinity to ignore invalid paths

if i == m - 1 and j == n - 1:Base case: at princess cell, calculate minimum health needed here

down = dfs(i + 1, j)Recursively compute health needed if moving down

right = dfs(i, j + 1)Recursively compute health needed if moving right

need = min(down, right) - dungeon[i][j]Calculate health needed at current cell based on next steps

return max(1, need)Health must be at least 1 to survive

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        return dfs(dungeon, 0, 0, m, n);
    }

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

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
    //     System.out.println(sol.calculateMinimumHP(dungeon)); // Output: 7
    // }
}

Line Notes

private int dfs(int[][] dungeon, int i, int j, int m, int n)Recursive helper to compute minimum health from cell (i,j)

if (i == m || j == n) return Integer.MAX_VALUE;Out-of-bounds returns max int to ignore invalid paths

if (i == m - 1 && j == n - 1)Base case at princess cell, compute minimum health needed

int down = dfs(dungeon, i + 1, j, m, n);Recursive call for moving down

int right = dfs(dungeon, i, j + 1, m, n);Recursive call for moving right

int need = Math.min(down, right) - dungeon[i][j];Calculate health needed at current cell

return Math.max(1, need);Ensure health is at least 1

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int m, n;
    vector<vector<int>> dungeon;

    int dfs(int i, int j) {
        if (i == m || j == n) return INT_MAX;
        if (i == m - 1 && j == n - 1) return max(1, 1 - dungeon[i][j]);
        int down = dfs(i + 1, j);
        int right = dfs(i, j + 1);
        int need = min(down, right) - dungeon[i][j];
        return max(1, need);
    }

    int calculateMinimumHP(vector<vector<int>>& dungeon_) {
        dungeon = dungeon_;
        m = dungeon.size();
        n = dungeon[0].size();
        return dfs(0, 0);
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
//     cout << sol.calculateMinimumHP(dungeon) << endl; // Output: 7
//     return 0;
// }

Line Notes

int dfs(int i, int j) {Recursive function to compute minimum health from cell (i,j)

if (i == m || j == n) return INT_MAX;Out-of-bounds returns max int to ignore invalid paths

if (i == m - 1 && j == n - 1) return max(1, 1 - dungeon[i][j]);Base case at princess cell

int down = dfs(i + 1, j);Recursive call moving down

int right = dfs(i, j + 1);Recursive call moving right

int need = min(down, right) - dungeon[i][j];Calculate health needed at current cell

return max(1, need);Ensure health is at least 1

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

// Example usage:
// console.log(calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]])); // Output: 7

Line Notes

function dfs(i, j) {Recursive helper to compute minimum health from cell (i,j)

if (i === m || j === n) return Infinity;Out-of-bounds returns Infinity to ignore invalid paths

if (i === m - 1 && j === n - 1) return Math.max(1, 1 - dungeon[i][j]);Base case at princess cell

const down = dfs(i + 1, j);Recursive call moving down

const right = dfs(i, j + 1);Recursive call moving right

const need = Math.min(down, right) - dungeon[i][j];Calculate health needed at current cell

return Math.max(1, need);Ensure health is at least 1

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each cell branches into two recursive calls (right and down), leading to exponential paths.

💡 For a 3x3 grid, this means up to 2^6=64 calls, which grows very fast for larger grids.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same states multiple times, drastically improving efficiency while preserving the recursive intuition.

Intuition

Use a cache to store the minimum health needed for each cell so that repeated calls return instantly instead of recomputing.

Algorithm

1. Initialize a memo dictionary or array to store results for each cell.
2. Modify the recursive function to check the memo before computing.
3. If the result is cached, return it immediately.
4. Otherwise, compute as before, store the result in memo, and return it.

💡 Memoization transforms exponential recursion into polynomial time by caching results.

Recurrence:dp(i,j) = max(1, min(dp(i+1,j), dp(i,j+1)) - dungeon[i][j])

</>

Code

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        memo = {}

        def dfs(i, j):
            if i == m or j == n:
                return float('inf')
            if i == m - 1 and j == n - 1:
                return max(1, 1 - dungeon[i][j])
            if (i, j) in memo:
                return memo[(i, j)]
            down = dfs(i + 1, j)
            right = dfs(i, j + 1)
            need = min(down, right) - dungeon[i][j]
            memo[(i, j)] = max(1, need)
            return memo[(i, j)]

        return dfs(0, 0)

# Example usage:
# sol = Solution()
# print(sol.calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]]))  # Output: 7

Line Notes

memo = {}Initialize memo dictionary to cache results

if (i, j) in memo:Check if result for cell (i,j) is already computed

memo[(i, j)] = max(1, need)Store computed minimum health needed for cell (i,j)

return memo[(i, j)]Return cached result to avoid recomputation

def dfs(i, j):Defines recursive function to compute minimum health from cell (i,j)

if i == m or j == n:Out-of-bounds returns infinity to ignore invalid paths

if i == m - 1 and j == n - 1:Base case at princess cell, compute minimum health needed

down = dfs(i + 1, j)Recursive call moving down

right = dfs(i, j + 1)Recursive call moving right

need = min(down, right) - dungeon[i][j]Calculate health needed at current cell

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] dungeon;
    private Map<String, Integer> memo = new HashMap<>();

    public int calculateMinimumHP(int[][] dungeon) {
        this.dungeon = dungeon;
        m = dungeon.length;
        n = dungeon[0].length;
        return dfs(0, 0);
    }

    private int dfs(int i, int j) {
        if (i == m || j == n) return Integer.MAX_VALUE;
        if (i == m - 1 && j == n - 1) return Math.max(1, 1 - dungeon[i][j]);
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);
        int down = dfs(i + 1, j);
        int right = dfs(i, j + 1);
        int need = Math.min(down, right) - dungeon[i][j];
        int res = Math.max(1, need);
        memo.put(key, res);
        return res;
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
    //     System.out.println(sol.calculateMinimumHP(dungeon)); // Output: 7
    // }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Memo map to cache results for each cell

String key = i + "," + j;Create unique key for cell (i,j) for memo lookup

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, res);Store computed result in memo

private int dfs(int i, int j)Recursive helper to compute minimum health from cell (i,j)

if (i == m || j == n) return Integer.MAX_VALUE;Out-of-bounds returns max int to ignore invalid paths

if (i == m - 1 && j == n - 1)Base case at princess cell, compute minimum health needed

int down = dfs(i + 1, j);Recursive call moving down

int right = dfs(i, j + 1);Recursive call moving right

int need = Math.min(down, right) - dungeon[i][j];Calculate health needed at current cell

#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int m, n;
    vector<vector<int>> dungeon;
    unordered_map<string, int> memo;

    string key(int i, int j) {
        return to_string(i) + "," + to_string(j);
    }

    int dfs(int i, int j) {
        if (i == m || j == n) return INT_MAX;
        if (i == m - 1 && j == n - 1) return max(1, 1 - dungeon[i][j]);
        string k = key(i, j);
        if (memo.count(k)) return memo[k];
        int down = dfs(i + 1, j);
        int right = dfs(i, j + 1);
        int need = min(down, right) - dungeon[i][j];
        memo[k] = max(1, need);
        return memo[k];
    }

    int calculateMinimumHP(vector<vector<int>>& dungeon_) {
        dungeon = dungeon_;
        m = dungeon.size();
        n = dungeon[0].size();
        return dfs(0, 0);
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
//     cout << sol.calculateMinimumHP(dungeon) << endl; // Output: 7
//     return 0;
// }

Line Notes

unordered_map<string, int> memo;Memo map to cache results

string k = key(i, j);Generate unique key for cell (i,j)

if (memo.count(k)) return memo[k];Return cached result if present

memo[k] = max(1, need);Store computed minimum health needed

int dfs(int i, int j)Recursive function to compute minimum health from cell (i,j)

if (i == m || j == n) return INT_MAX;Out-of-bounds returns max int to ignore invalid paths

if (i == m - 1 && j == n - 1) return max(1, 1 - dungeon[i][j]);Base case at princess cell

int down = dfs(i + 1, j);Recursive call moving down

int right = dfs(i, j + 1);Recursive call moving right

int need = min(down, right) - dungeon[i][j];Calculate health needed at current cell

var calculateMinimumHP = function(dungeon) {
    const m = dungeon.length, n = dungeon[0].length;
    const memo = new Map();
    function key(i, j) { return i + ',' + j; }
    function dfs(i, j) {
        if (i === m || j === n) return Infinity;
        if (i === m - 1 && j === n - 1) return Math.max(1, 1 - dungeon[i][j]);
        const k = key(i, j);
        if (memo.has(k)) return memo.get(k);
        const down = dfs(i + 1, j);
        const right = dfs(i, j + 1);
        const need = Math.min(down, right) - dungeon[i][j];
        const res = Math.max(1, need);
        memo.set(k, res);
        return res;
    }
    return dfs(0, 0);
};

// Example usage:
// console.log(calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]])); // Output: 7

Line Notes

const memo = new Map();Initialize memo map to cache results

function key(i, j) { return i + ',' + j; }Create unique key for memo lookup

if (memo.has(k)) return memo.get(k);Return cached result if available

memo.set(k, res);Store computed result in memo

function dfs(i, j) {Recursive helper to compute minimum health from cell (i,j)

if (i === m || j === n) return Infinity;Out-of-bounds returns Infinity to ignore invalid paths

if (i === m - 1 && j === n - 1) return Math.max(1, 1 - dungeon[i][j]);Base case at princess cell

const down = dfs(i + 1, j);Recursive call moving down

const right = dfs(i, j + 1);Recursive call moving right

const need = Math.min(down, right) - dungeon[i][j];Calculate health needed at current cell

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memo and recursion stack

Each cell is computed once and stored, avoiding repeated work.

💡 For a 200x200 grid, this means 40,000 computations, which is efficient.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs while keeping recursion intuitive.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the destination backwards, which is often easier to debug and understand than recursion.

Intuition

Create a dp table where dp[i][j] stores the minimum health needed to enter cell (i,j). Fill the table starting from the bottom-right corner up to the top-left.

Algorithm

1. Initialize a dp table with dimensions (m+1) x (n+1) filled with infinity to handle boundaries.
2. Set dp[m][n-1] and dp[m-1][n] to 1 as base cases representing the health needed just beyond the princess cell.
3. Iterate from bottom-right to top-left, computing dp[i][j] using the recurrence.
4. Return dp[0][0] as the minimum initial health needed.

💡 The extra row and column simplify boundary conditions, making the code cleaner.

Recurrence:dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

</>

Code

from typing import List

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] = 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(1, need)

        return dp[0][0]

# Example usage:
# sol = Solution()
# print(sol.calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]]))  # Output: 7

Line Notes

dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]Initialize dp with infinity to handle boundaries

dp[m][n - 1] = 1Set base case for cell just right of princess

dp[m - 1][n] = 1Set base case for cell just below princess

for i in range(m - 1, -1, -1):Iterate rows bottom to top

for j in range(n - 1, -1, -1):Iterate columns right to left

need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]Calculate health needed at current cell

dp[i][j] = max(1, need)Ensure health is at least 1

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++)
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        dp[m][n - 1] = 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(1, need);
            }
        }
        return dp[0][0];
    }

    // Example usage:
    // public static void main(String[] args) {
    //     Solution sol = new Solution();
    //     int[][] dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
    //     System.out.println(sol.calculateMinimumHP(dungeon)); // Output: 7
    // }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Create dp table with extra row and column

Arrays.fill(dp[i], Integer.MAX_VALUE);Initialize dp cells to max int for boundaries

dp[m][n - 1] = 1;Base case for cell right of princess

dp[m - 1][n] = 1;Base case for cell below princess

for (int i = m - 1; i >= 0; i--)Iterate rows bottom to top

for (int j = n - 1; j >= 0; j--)Iterate columns right to left

dp[i][j] = Math.max(1, need);Ensure health is at least 1

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

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] = 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(1, need);
            }
        }
        return dp[0][0];
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     vector<vector<int>> dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
//     cout << sol.calculateMinimumHP(dungeon) << endl; // Output: 7
//     return 0;
// }

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));Initialize dp with INT_MAX for boundaries

dp[m][n - 1] = 1;Base case for cell right of princess

dp[m - 1][n] = 1;Base case for cell below princess

for (int i = m - 1; i >= 0; i--)Iterate rows bottom to top

for (int j = n - 1; j >= 0; j--)Iterate columns right to left

dp[i][j] = max(1, need);Ensure health is at least 1

var calculateMinimumHP = function(dungeon) {
    const m = dungeon.length, n = dungeon[0].length;
    const dp = Array(m + 1).fill(0).map(() => 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(1, need);
        }
    }
    return dp[0][0];
};

// Example usage:
// console.log(calculateMinimumHP([[-2,-3,3],[-5,-10,1],[10,30,-5]])); // Output: 7

Line Notes

const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(Infinity));Initialize dp with Infinity for boundaries

dp[m][n - 1] = 1;Base case for cell right of princess

dp[m - 1][n] = 1;Base case for cell below princess

for (let i = m - 1; i >= 0; i--)Iterate rows bottom to top

for (let j = n - 1; j >= 0; j--)Iterate columns right to left

dp[i][j] = Math.max(1, need);Ensure health is at least 1

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill each cell once in the dp table.

💡 For a 200x200 grid, this means 40,000 operations, which is efficient and practical.

Interview Verdict: Accepted

This is the optimal and most common approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up DP (Approach 3) is usually best, but understanding brute force and memoization is essential for full comprehension.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n) memo + recursion stack	Possible but less likely	Yes	Good to explain and sometimes code
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Best approach to code in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Clarify the problem constraints and what is being asked.Explain the brute force recursive approach to show understanding of the problem.Introduce memoization to optimize recursion and avoid repeated work.Present the bottom-up DP tabulation as the optimal solution.Discuss time and space complexities and possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify overlapping subproblems, implement DP correctly, and optimize from brute force to efficient solutions.

Common Follow-ups

• What if the knight can move in all four directions? → The problem becomes more complex and may require graph algorithms.
• Can you optimize space usage? → Yes, by using a 1D dp array since only the next row and current row are needed.

💡 These follow-ups test your ability to adapt the solution to variations and optimize further.

🔍

Pattern Recognition

When to Use

1) Problem involves grid traversal with constraints; 2) Need to minimize or maximize a value; 3) Health or cost can be negative or positive; 4) Movement restricted to right/down or similar.

Signature Phrases

minimum initial healthonly move right or downnever drop to zero or below

NOT This Pattern When

Problems that require forward DP without backward reasoning or those with unrestricted movement are different patterns.

Similar Problems

Minimum Path Sum - similar grid DP but sums values instead of health constraintsUnique Paths II - grid traversal with obstacles, simpler DPCoin Change - DP with minimum coins, similar minimization concept

Practice

1. Consider the following bottom-up DP code for the Triangle minimum path sum problem. Given the input triangle = [[2],[3,4],[6,5,7]], what is the value of dp after the first iteration of the outer loop (i = 1)?

easy

A. [8, 9, 7]

B. [9, 10, 7]

C. [11, 10, 7]

D. [7, 9, 7]

Solution

1. Step 1: Initialize dp with last row

   dp = [6, 5, 7]

2. Step 2: Compute dp for i=1 (row [3,4])

   For j=0: dp[0] = 3 + min(6,5) = 3 + 5 = 8 For j=1: dp[1] = 4 + min(5,7) = 4 + 5 = 9 Updated dp = [8, 9, 7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp updated correctly for row 1 [OK]

Hint: dp[j] updated using min of dp[j], dp[j+1] from row below [OK]

Common Mistakes:

• Off-by-one error in indexing dp
• Not copying last row correctly
• Mixing up dp[j] and dp[j+1] in min calculation

2. What is the time complexity of the space-optimized bottom-up DP solution for the Maximal Square problem on an m x n matrix, and why might some candidates incorrectly think it is higher?

medium

A. O(m^3) because checking all squares requires nested loops

B. O(m * n * min(m,n)) because of checking all possible square sizes

C. O(m * n) because each cell is processed once with constant time updates

D. O(m + n) because only rows and columns are iterated separately

Solution

1. Step 1: Identify loops in the code

   Two nested loops iterate over rows and columns, each cell processed once.

2. Step 2: Understand DP update cost

   Each dp update is O(1), no nested checks for squares inside loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP avoids checking all squares explicitly [OK]

Hint: DP processes each cell once with constant work [OK]

Common Mistakes:

• Confusing brute force with DP complexity
• Assuming nested loops check all squares
• Ignoring constant time DP updates

3. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

4. What is the time complexity of the bottom-up DP solution for the Strange Printer problem after string compression, where m is the length of the compressed string?

medium

A. O(m^2)

B. O(m^3)

C. O(n^3) where n is original string length

D. O(m^2 * log m)

Solution

1. Step 1: Identify loops in bottom-up DP

   There are three nested loops: length (1 to m), start index i (up to m), and partition index k (between i and j), each up to m.

2. Step 2: Calculate complexity

   Overall complexity is O(m * m * m) = O(m^3). Compression reduces n to m, so complexity depends on compressed length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over compressed length m [OK]

Hint: Three nested loops over compressed string length cause cubic time [OK]

Common Mistakes:

• Confusing original length n with compressed length m
• Forgetting the inner loop over k

5. Examine the following buggy code snippet from the Zuma Game solution. Which line contains the subtle bug that causes incorrect minimal moves calculation?

medium

A. Line with 'new_s = s[:i] + s[j:] # BUG: missing recursive removal'

B. Line with 'balls_needed = 3 - (j - i)'

C. Line with 'hand_count[s[i]] -= balls_needed'

D. Line with 'if temp != -1:'

Solution

1. Step 1: Identify role of remove_consecutive

   After insertion and removal, consecutive balls must be recursively removed to handle chain reactions.

2. Step 2: Locate missing recursive removal

   The line creating new_s omits calling remove_consecutive, so chain reactions are not processed, leading to incorrect board states and minimal moves.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing recursive removal causes wrong minimal moves [OK]

Hint: Missing recursive removal breaks chain reaction logic [OK]

Common Mistakes:

• Forgetting to call remove_consecutive after insertion
• Incorrectly adjusting hand counts
• Miscomputing balls needed for removal