LeetCode 174: Dungeon Game ·

基本資料
#

難易度: hard 第一次嘗試：2026-06-30 來源：Day 31 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 174: pass after wording repair
LC 221 and LC 174 are both 2D DP, but they are not the same recurrence family as the earlier grid problems.
explain LC 174 with reverse DP and the minimum required health on entry state

當天筆記摘錄
#

Problem 2 - LC 174 Dungeon Game
#

Pattern: reverse 2D DP with minimum required resource.

Why This Fits
#

Forward DP feels tempting but usually creates the wrong state question.

The real requirement is not:

what is the best health after arriving here?

It is:

what minimum health must I have when entering this cell so that I can still survive to the goal?

That naturally points backward from the destination.

Core State / Invariant
#

dp[r][c] = minimum health required upon entering cell (r, c) to guarantee survival through the destination

This is the interview-safe state because it encodes the safety guarantee directly.

Transition
#

Let the cheaper required next state be:

need_next = min(dp[r + 1][c], dp[r][c + 1])

Then:

dp[r][c] = max(1, need_next - dungeon[r][c])

Why:

if the current cell gives health, required entry health can drop
if the current cell deals damage, required entry health rises
health can never be below 1

Base Case
#

At the destination:

dp[last_row][last_col] = max(1, 1 - dungeon[last_row][last_col])

Reason:

after processing the last cell, the knight must still have at least 1 health

Complexity
#

Time: O(m * n)
Space: O(m * n)

Can be compressed to:

Space: O(n)

Common Mistakes
#

trying to maximize remaining health instead of minimizing required entry health
doing forward DP with an unstable state
forgetting the clamp to 1
using max(down, right) instead of min(down, right) for the required next state
getting the destination base case wrong

Strong Spoken Explanation
#

I solve this backward because the meaningful state is the minimum health required when entering a cell so that I can still reach the princess alive. From each cell, I only care about the cheaper of the two required next states, right or down. Then I subtract the current cell value because healing reduces the needed entry health and damage increases it. Finally I clamp the result to at least 1, because the knight can never be dead or at zero health.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [float('inf')] * (n + 1)
        dp[n - 1] = 1

        for r in range(m - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                need = min(dp[c], dp[c + 1]) - dungeon[r][c]
                dp[c] = max(1, need)

        return dp[0]