leetcode hard : Dungeon Game

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

Dungeon Game - LeetCode

그리드, 최소값, 오른쪽 or 아래쪽.. 어디서 많이보던 키워드들

누가 봐도 DP다!

 

i,j에서 출발하면 도착지점까지 hp가 얼마나 필요할까를 기준으로 잡는다.

즉 정답은 search(0,0)이다. 0,0에서 출발할거니까.

현재 위치 기준으로 오른쪽으로 갔을때의 필요hp랑 아래쪽으로 갔을때의 필요hp를 구하고 그중에서 작은값을 구한다.

구한값에 dungeon[i][j]를 빼면 현재 위치에서의 필요 hp가 나오는데

필요 hp가 0이하인 경우는 와도 체력이 안깎인다는거다. 근데 최소 1은 필요하니까 1이랑 비교해서 더 큰값을 현재위치까지 오기위한 필요hp로 계산하면 된다.

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        N = len(dungeon)
        M = len(dungeon[0])
        dp = [[10**9] * M for _ in range(N)]

        def search(i, j):
            if i == N or j == M:
                return 10**9
            if i == N - 1 and j == M - 1:
                return 1 if dungeon[i][j] > 0 else -dungeon[i][j] + 1
            if dp[i][j] != 10**9:
                return dp[i][j]

            right = search(i, j+1)
            down = search(i+1, j)
            
            here = min(down, right) - dungeon[i][j]
            dp[i][j] = max(here, 1)
            return dp[i][j]

        return search(0, 0)

O(NM)