騎士從左上角出發、走到右下角救公主，每步只能往右或往下。格子有正值（加血）或負值（扣血），任何時刻血量 ≤ 0 就死。求出發時最少需要多少初始血量（全程血量需 ≥ 1）。
Example:
Input: dungeon = [[-2,-3,3], [-5,-10,1], [10,30,-5]] Output: 7（最佳路徑：右→右→下→下，初始 7 血剛好全程 ≥ 1）
Intuition
TIP
核心思路：必須從右下往左上反推。某格所需的最低進入血量，取決於「往右或往下兩個方向中、較省的那個未來需求」，再扣掉本格數值。正向走無法決定，因為當前需求依賴未來。
dp[i][j]= 進入(i,j)前所需的最低血量（保證後續都 ≥ 1）- 轉移：
need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j] - 若
need ≤ 0代表本格加血夠多，最低需求夾到1 - 為什麼反向：正向時「現在帶多少血」會影響後面，無法用單一狀態表達；反向「未來最少要多少」才有最佳子結構
Approaches
1. Memoized Recursion (Top-Down) — O(m·n) / O(m·n)
- Idea:
dp(i,j)= 從(i,j)走到終點所需的最低進入血量，遞迴取右/下較省者，memo 快取 - Time:
O(m·n)- 每格算一次 - Space:
O(m·n)- memo + 遞迴堆疊
class Solution {
fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
val m = dungeon.size; val n = dungeon[0].size
val memo = Array(m) { IntArray(n) } // 0 = 未算
fun dp(i: Int, j: Int): Int {
if (i >= m || j >= n) return Int.MAX_VALUE
if (i == m - 1 && j == n - 1) return maxOf(1, 1 - dungeon[i][j])
if (memo[i][j] != 0) return memo[i][j]
val need = minOf(dp(i + 1, j), dp(i, j + 1)) - dungeon[i][j]
memo[i][j] = if (need <= 0) 1 else need
return memo[i][j]
}
return dp(0, 0)
}
}⭐ 2. DP from Bottom-Right (Bottom-Up) — O(m·n) / O(m·n)
- Idea:
dp[i][j]是進入該格所需最低血量，從終點反推 - Time:
O(m·n) - Space:
O(m·n)（可滾動成O(n)）
class Solution {
fun calculateMinimumHP(dungeon: Array<IntArray>): Int {
val m = dungeon.size; val n = dungeon[0].size
// 多一圈哨兵設為極大，終點右側/下方視為「只需 1 血」
val dp = Array(m + 1) { IntArray(n + 1) { Int.MAX_VALUE } }
dp[m][n - 1] = 1
dp[m - 1][n] = 1
for (i in m - 1 downTo 0) {
for (j in n - 1 downTo 0) {
val need = minOf(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
dp[i][j] = if (need <= 0) 1 else need
}
}
return dp[0][0]
}
}🔑 Takeaways
- Pattern: 網格 DP，但方向反過來（從終點往起點推）
- Key trick: 當「當前狀態取決於未來」時正向 DP 失效，要逆向定義「未來最少需求」；
max(1, …)確保血量全程 ≥ 1。對照 64 Minimum Path Sum（可正向）即能體會何時必須反向