Dungeon Game

📋

Problem

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.

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

Edge cases: Single cell with positive value → minimum initial health is 1Single cell with negative value → minimum initial health is 1 - cell valueAll cells zero → minimum initial health is 1

</>

IDE

def calculateMinimumHP(dungeon: List[List[int]]) -> int:public int calculateMinimumHP(int[][] dungeon)int calculateMinimumHP(vector<vector<int>>& dungeon)function calculateMinimumHP(dungeon)

def calculateMinimumHP(dungeon):
    # Write your solution here
    pass

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    // Write your solution here
    return 0;
}

function calculateMinimumHP(dungeon) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Not clamping minimum health to 1, allowing zero or negative health.✅ Use max(1, calculated_health) at every DP step to ensure health never drops below 1.

Wrong: Incorrect low values (e.g., 3 instead of 7)Using greedy approach picking only one path (right or down) instead of minimum of both.✅ At each cell, take min of dp[i+1][j] and dp[i][j+1] to consider all paths.

Wrong: Too high values (e.g., 10 instead of 7)Not taking minimum of next steps, or adding dungeon[i][j] instead of subtracting.✅ Use dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) correctly.

Wrong: Timeout or no outputUsing brute force recursion without memoization or DP.✅ Implement DP with memoization or bottom-up tabulation to achieve O(m*n) time.

✓

Test Cases

Focus on base cases and smallest inputs to solidify your DP foundation.

Test your solution against tricky inputs that expose greedy or off-by-one errors.

Optimize your solution to run efficiently on large inputs using bottom-up DP.

t1_01basic

Input{"dungeon":[[-2,-3,3],[-5,-10,1],[10,30,-5]]}

Expected7

⏱ Performance - must finish in 2000ms

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

💡 Think about working backwards from the princess to the knight.

💡 Use dynamic programming to compute minimum health needed at each cell.

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

Why it failed: Incorrect output means the DP recurrence is wrong or boundary conditions are mishandled. Fix by ensuring dp values never drop below 1 and correctly handle bottom-right cell.

✓ Correctly computes minimum initial health using bottom-up DP.

t1_02basic

Input{"dungeon":[[0,-3],[-10,0]]}

Expected4

⏱ Performance - must finish in 2000ms

Minimum initial health 4 allows path (right, down) without health dropping below 1.

💡 Check how negative cells affect minimum health needed.

💡 Remember to take the minimum of right and down paths at each cell.

💡 Apply dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) carefully.

Why it failed: Failing this test usually means not taking the minimum of next steps or not clamping health to at least 1. Fix by applying min and max correctly in DP.

✓ Handles negative and zero cells correctly in DP.

t2_01edge

Input{"dungeon":[[5]]}

Expected1

⏱ Performance - must finish in 2000ms

Single positive cell requires minimum initial health 1.

💡 Consider the simplest case of a single cell.

💡 Positive cell means no health loss, so minimum health is 1.

💡 Ensure base case returns max(1, 1 - dungeon[m-1][n-1]).

Why it failed: If output > 1, code incorrectly subtracts positive cell value. Fix by using max(1, 1 - cell_value) at bottom-right cell.

✓ Correctly handles single positive cell base case.

t2_02edge

Input{"dungeon":[[-7]]}

Expected8

⏱ Performance - must finish in 2000ms

Single negative cell requires initial health 1 - (-7) = 8.

💡 Single cell with negative value requires health to offset damage.

💡 Minimum health is 1 minus the negative cell value.

💡 Check base case calculation for bottom-right cell.

Why it failed: If output < 8, code fails to add 1 to offset damage. Fix by returning max(1, 1 - dungeon[m-1][n-1]) for single cell.

✓ Correctly handles single negative cell base case.

t2_03edge

Input{"dungeon":[[0,0],[0,0]]}

Expected1

⏱ Performance - must finish in 2000ms

All zero cells require minimum initial health 1.

💡 Zero cells do not affect health negatively.

💡 Minimum health should never drop below 1.

💡 Ensure DP clamps health to at least 1 at every cell.

Why it failed: If output > 1, code incorrectly reduces health below 1. Fix by applying max(1, ...) at each DP step.

✓ Correctly handles all zero cells.

t3_01corner

Input{"dungeon":[[-2,-3,3],[-5,-10,1],[10,30,-50]]}

Expected52

⏱ Performance - must finish in 2000ms

Large negative value at bottom-right requires high initial health to survive.

💡 Check how large negative values at the end affect initial health.

💡 DP must consider worst-case path damage, not just shortest path.

💡 Ensure dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) handles large negatives.

Why it failed: If output < 52, code ignores large negative cell or uses greedy approach. Fix by correctly computing min health needed from both directions.

✓ Correctly handles large negative values at destination.

t3_02corner

Input{"dungeon":[[-2,-3,3],[-5,-10,1],[10,30,-5],[0,0,-1]]}

Expected7

⏱ Performance - must finish in 2000ms

Extra row with zeros and a small negative at end does not reduce initial health below 7.

💡 Adding rows with zeros should not reduce minimum health needed.

💡 DP must consider all paths, not just greedy shortest path.

💡 Check that dp uses min of right and down paths correctly.

Why it failed: If output < 7, code uses greedy approach picking only right moves. Fix by considering both right and down moves in DP.

✓ Avoids greedy trap by considering all paths.

t3_03corner

Input{"dungeon":[[-1,-1],[-1,-1]]}

Expected3

⏱ Performance - must finish in 2000ms

Uniform negative values require initial health 3 to survive any path.

💡 Uniform negatives test if DP correctly accumulates damage.

💡 Check that DP does not confuse 0/1 knapsack logic with this problem.

💡 Ensure health never drops below 1 at any cell.

Why it failed: If output < 3, code confuses problem with unbounded knapsack or ignores cumulative damage. Fix by correctly accumulating minimum health needed.

✓ Correctly accumulates damage over uniform negative cells.

t4_01performance

Input{"dungeon":[[-1000,-999,-998,-997,-996,-995,-994,-993,-992,-991,-990,-989,-988,-987,-986,-985,-984,-983,-982,-981],[-980,-979,-978,-977,-976,-975,-974,-973,-972,-971,-970,-969,-968,-967,-966,-965,-964,-963,-962,-961],[-960,-959,-958,-957,-956,-955,-954,-953,-952,-951,-950,-949,-948,-947,-946,-945,-944,-943,-942,-941],[-940,-939,-938,-937,-936,-935,-934,-933,-932,-931,-930,-929,-928,-927,-926,-925,-924,-923,-922,-921],[-920,-919,-918,-917,-916,-915,-914,-913,-912,-911,-910,-909,-908,-907,-906,-905,-904,-903,-902,-901],[-900,-899,-898,-897,-896,-895,-894,-893,-892,-891,-890,-889,-888,-887,-886,-885,-884,-883,-882,-881],[-880,-879,-878,-877,-876,-875,-874,-873,-872,-871,-870,-869,-868,-867,-866,-865,-864,-863,-862,-861],[-860,-859,-858,-857,-856,-855,-854,-853,-852,-851,-850,-849,-848,-847,-846,-845,-844,-843,-842,-841],[-840,-839,-838,-837,-836,-835,-834,-833,-832,-831,-830,-829,-828,-827,-826,-825,-824,-823,-822,-821],[-820,-819,-818,-817,-816,-815,-814,-813,-812,-811,-810,-809,-808,-807,-806,-805,-804,-803,-802,-801],[-800,-799,-798,-797,-796,-795,-794,-793,-792,-791,-790,-789,-788,-787,-786,-785,-784,-783,-782,-781],[-780,-779,-778,-777,-776,-775,-774,-773,-772,-771,-770,-769,-768,-767,-766,-765,-764,-763,-762,-761],[-760,-759,-758,-757,-756,-755,-754,-753,-752,-751,-750,-749,-748,-747,-746,-745,-744,-743,-742,-741],[-740,-739,-738,-737,-736,-735,-734,-733,-732,-731,-730,-729,-728,-727,-726,-725,-724,-723,-722,-721],[-720,-719,-718,-717,-716,-715,-714,-713,-712,-711,-710,-709,-708,-707,-706,-705,-704,-703,-702,-701],[-700,-699,-698,-697,-696,-695,-694,-693,-692,-691,-690,-689,-688,-687,-686,-685,-684,-683,-682,-681],[-680,-679,-678,-677,-676,-675,-674,-673,-672,-671,-670,-669,-668,-667,-666,-665,-664,-663,-662,-661],[-660,-659,-658,-657,-656,-655,-654,-653,-652,-651,-650,-649,-648,-647,-646,-645,-644,-643,-642,-641],[-640,-639,-638,-637,-636,-635,-634,-633,-632,-631,-630,-629,-628,-627,-626,-625,-624,-623,-622,-621],[-620,-619,-618,-617,-616,-615,-614,-613,-612,-611,-610,-609,-608,-607,-606,-605,-604,-603,-602,-601]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 20x20 grid with large negative values to test O(m*n) DP performance within 2 seconds.

💡 Brute force recursion will time out on large grids.

💡 Use bottom-up DP with O(m*n) time complexity.

💡 Precompute dp from bottom-right to top-left to optimize.

Why it failed: TLE indicates brute force or exponential recursion used. Fix by implementing DP with memoization or tabulation.

✓ Efficient O(m*n) DP solution passes performance test.

Practice

1. You are given an array of balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears and adjacent balloons become neighbors. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. Greedy approach bursting the balloon with the highest number first

B. Sorting balloons and bursting them in ascending order

C. Dynamic programming using interval partitioning and considering the last balloon to burst in each interval

D. Simple recursion trying all burst orders without memoization

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing coins by bursting balloons in an order where each burst depends on adjacent balloons, which changes dynamically.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because local choices don't guarantee global optimum. Simple recursion is correct but inefficient. Interval DP solves by considering subproblems defined by intervals and choosing the last balloon to burst in each interval, ensuring optimal substructure.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Interval DP handles overlapping subproblems and changing neighbors [OK]

Hint: Optimal substructure requires interval DP, not greedy [OK]

Common Mistakes:

• Assuming greedy bursting yields max coins
• Trying recursion without memoization
• Ignoring interval-based subproblems

2. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

3. You are given a convex polygon with n vertices, each vertex having an associated value. The goal is to triangulate the polygon such that the sum of the products of the values of the vertices of each triangle is minimized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Divide and conquer by splitting the polygon into two halves and solving independently

B. A greedy algorithm that always picks the triangle with the smallest immediate product first

C. A simple depth-first search without memoization that explores all triangulations

D. Dynamic programming over intervals that considers all possible triangulations and chooses the minimal cost

Solution

1. Step 1: Understand problem structure

   The problem requires considering all possible triangulations to find the minimal sum of triangle costs, which depends on intervals of vertices.

2. Step 2: Identify suitable algorithm

   Dynamic programming over intervals (interval DP) systematically explores all sub-polygons and stores minimal costs, ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interval DP is the classic approach for polygon triangulation problems [OK]

Hint: Interval DP handles overlapping subproblems optimally [OK]

Common Mistakes:

• Greedy fails due to local minima
• DFS without memoization is exponential
• Divide and conquer ignores polygon connectivity

4. What is the time complexity of the bottom-up DP solution for the Cherry Pickup problem on an n x n grid, where dp is a 3D array indexed by step and two row positions of the players?

medium

A. O(4^n) due to exploring all possible paths for two players

B. O(n^3) because there are O(n) steps and O(n^2) states for the two players' rows, each computed in constant time

C. O(n^4) since for each dp state, four previous states are checked

D. O(n^2) as the dp only tracks positions of two players without step dimension

Solution

1. Step 1: Identify number of states

   There are 2n-1 steps, and for each step, possible row positions for player 1 and player 2 are each O(n), so total states are O(n^3).

2. Step 2: Analyze transitions per state

   Each dp state checks up to 4 previous states in O(1) time, so total time is O(n^3).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3D dp with O(n^3) states and constant transitions [OK]

Hint: Count states x transitions carefully [OK]

Common Mistakes:

• Confusing number of states with number of transitions
• Assuming exponential time due to recursion
• Ignoring that step dimension limits valid states

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