[LeetCode] 174. Dungeon Game

Problem : https://leetcode.com/problems/dungeon-game/

Memorization Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        @lru_cache(maxsize = None)
        def helper(y, x):
            if y >= row or x >= col:
                return 2 ** 31 - 1
            
            if y == row -1 and x == col - 1:
                return max(1, 1 - dungeon[y][x])
            
            # only need to have 1 health point to survive 
            return max(1, min(helper(y,x+1), helper(y+1, x)) - dungeon[y][x])

        return helper(0, 0)

DP Solution:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        row = len(dungeon)
        col = len(dungeon[0])
        
        max_int = 2 ** 31 - 1
        
        dp = [[max_int] * (col+1) for _ in range(row + 1)]
        
        dp[row][col-1] = 1
        dp[row-1][col] = 1
        
        for y in reversed(range(row)):
            for x in reversed(range(col)):
                dp[y][x] = max(1, min(dp[y+1][x], dp[y][x+1]) - dungeon[y][x])
        
        return dp[0][0]