🌱 Keegan's Digital Garden

174. Dungeon Game

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- princess is captured at the bottom right corner of matrix 
- each cell in the matrix is a room 
- start at the top left position (0,0) 
- each room can either decrease, increase or leave the knights health unchanged
- knight can only move down or right each move - return the minimum initial health so that they can rescue the princess 

* usually when i see that you can only move down or right, i think of a DFS approach 
* however this is not the same, as we are one trying to find the cheapest path and also need to calculate the minimum STARTING health 
* i wonder if starting from the end and moving back to the top left would be good * 5 + (-1) + (-3) + 3 + 2 (need to add one so that we always stay above 0?) 
* maybe a dp recursive approach that starts from the top and works down

🤔What Did I Struggle With?

~

💡 Explanation of Solution

DP Bottom-Up Appoach:
work backward from the princess's location (bottom right) and compute the minimum health required at each cell to survive

1. define dp[i][j]
	- represents the minimum health needed at cell (i,j) to ensure survival when reaching the princess

2. base case (bottom right corner)
	- the knight MUST have at least 1hp when entering the princess's cell
	- if the room has a positive value, the knight still needs at least 1hp
	- formula: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])

3. bottom-up transition
	- the knight can only move right or down, so at each cell (i,j), we determine 
		- the minimum HP required for the next move (min(dp[i+1][j], dp[i][j+1]))
		- the required HP at (i,j): max(1, min_next_step - dungeon[i][j])
	- this ensures that the knight never drops below 1HP

4. final answer
	- dp[0][0] gives the minimum starting health

⌛ Complexity Analysis

Time Complexity: O(n*m)
- we iterate through the m*n matrix once 

Space Complexity: O(n*m)
- use of DP table

💻 Implementation of Solution

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
 
        // Base Case: Bottom-right cell (Princess's Room)
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
 
        // Fill last row (only move right)
        for (int j = n - 2; j >= 0; --j) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
 
        // Fill last column (only move down)
        for (int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
 
        // Fill the rest of the DP table (bottom-up)
        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                int min_next_step = min(dp[i + 1][j], dp[i][j + 1]); // Choose the best path
                dp[i][j] = max(1, min_next_step - dungeon[i][j]);
            }
        }
 
        return dp[0][0]; // Minimum initial health required
    }
};

Graph View