Dungeon Game — Reverse Grid DP

Problem

Grid with positive/negative values. Knight starts at top-left, must reach bottom-right with HP > 0 at all times. Find minimum initial HP.

Approach — Reverse DP

Work backwards from bottom-right. dp[i][j] = min HP needed entering cell (i,j) to survive from here to end.

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

Time: O(mn) | Space: O(mn)

Solutions

Python

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

Complexity

• Time: O(mn) | Space: O(mn)