174. Dungeon Game

[zeikar]

Problem link

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

Problem Summary

2차원 던전이 있고 가장 오른쪽 아래의 공주를 구해야 한다.
각 배열의 값에 해당하는 만큼의 체력이 깎이거나 증가될 때, 공주를 구하려면 필요한 최소의 체력을 구하는 문제.

Solution

전형적인 DP이다.
특히 거꾸로 올라가는 방향이 없을 경우 (이 문제에서는 오른쪽와 아래 방향으로만 갈 수 있다) 거의 DP로 풀 수 있다.

DP[x][y] = x, y 칸으로 가기 위한 최소의 체력

으로 정의하면 DP[x][y] = min(DP[x+1][y], DP[x][y + 1]) 이런 느낌으로 top-down DP를 짤 수 있다. 여기서는 체력이 최소 1 이상 남겨야 하므로 이것만 처리해주면 된다.

Source Code

from functools import lru_cache
from typing import List


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

        @lru_cache(None)
        def get_min_hp(x, y):
            if x == m - 1 and y == n - 1:
                return max(1, -dungeon[x][y] + 1)

            if x == m - 1:
                return max(1, -dungeon[x][y] + get_min_hp(x, y + 1))

            if y == n - 1:
                return max(1, -dungeon[x][y] + get_min_hp(x + 1, y))

            return min(max(1, -dungeon[x][y] + get_min_hp(x + 1, y)), max(1, -dungeon[x][y] + get_min_hp(x, y + 1)))

        return get_min_hp(0, 0)