Leetcode 174 Solution

This article provides solution to leetcode question 174 (dungeon-game)
Categories:
Tags:
Access this page by simply typing in "lcs 174" in your browser address bar if you have bunnylol configured.

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

Solution

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

        dp = [[0 for _ in range(n)] for _ in range(m)]

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

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                options = []

                if i < m - 1:
                    options.append(max(1, dp[i + 1][j] - dungeon[i][j]))
                if j < n - 1:
                    options.append(max(1, dp[i][j + 1] - dungeon[i][j]))

                if options:
                    dp[i][j] = min(options)

        return dp[0][0]