[LeetCode][Python3] 174. Dungeon Game

Problem :

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

My Solution :

class Solution:

def calculateMinimumHP(self, dungeon):

M, N = len(dungeon), len(dungeon[0])

HP = [[float('INF')]*(N+1) for _ in range(M+1)]

HP[M][N-1] = HP[M-1][N] = 1

for r in range(M-1, -1, -1):

for c in range(N-1, -1, -1):

need = min(HP[r+1][c], HP[r][c+1]) - dungeon[r][c]

HP[r][c] = need if need > 1 else 1

return HP[0][0]

Comment :

도착점부터 거꾸로 시작점까지 올라가며 계산하는 DP 문제