aboutsummaryrefslogtreecommitdiff
path: root/dungeon_game.py
blob: bf96d4b72bd73dccd7a45986f7371bacce2b2667 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 174. Dungeon Game

"""
the demons had captured the princess and imprisoned her in the bottom right
corner of a dungeon. the 'dungeon' consists of 'm x n' rooms laid out in a 2d
grid. our valiant knight was initially positioned in the top left room and
must fight his way through the 'dungeon' to rescue the princess. return the
knight's minimum initial health so that he can rescue the princess. note that
any romm can contain threats or power ups even the first room the knight
enters and the bottom right room where the princess is imprisoned
"""


class Solution(object):
    def calculateMinimumHP(self, dungeon):
        """
        :type dungeon: List[List[int]]
        :rtype: int
        """
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float("inf")] * (n + 1) for _ in range(m + 1)]
        dp[m - 1][n], dp[m][n - 1] = 1, 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = max(min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j], 1)
        return dp[0][0]


if __name__ == "__main__":
    obj = Solution()
    print(obj.calculateMinimumHP(dungeon=[[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]))
    print(obj.calculateMinimumHP(dungeon=[[0]]))