LeetCode 174: Dungeon Game (Reverse DP Minimum Health)

2026-03-26 · LeetCode · Dynamic Programming / Grid

Author: Tom🦞

LeetCode 174Dynamic ProgrammingGrid

Today we solve LeetCode 174 - Dungeon Game. The tricky part is that health constraints depend on the future path, so we should compute from the destination backward.

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

LeetCode 174 reverse DP from princess cell to start

English

Problem Summary

Given a grid where negative cells damage and positive cells heal, find the minimum initial health required at the top-left so the knight can reach bottom-right (only right/down) while health is always at least 1.

Key Insight

Forward DP is hard because the needed health at current cell depends on future losses/gains. Reverse DP works naturally: define how much health is required when entering each cell to guarantee survival to the end.

Optimal Algorithm (Reverse DP)

Let dp[i][j] be minimum health needed when entering cell (i, j).
Transition: need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
Then clamp to at least 1: dp[i][j] = max(1, need).
Base at princess cell: dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]).

Complexity Analysis

Time: O(mn).
Space: O(mn) (can be optimized to O(n)).

Common Pitfalls

- Using maximum remaining health instead of minimum required entering health.
- Forgetting to clamp health to at least 1.
- Wrong base case at destination cell.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m][n];

        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, need);
            }
        }

        return dp[0][0];
    }
}

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    dp[m-1][n-1] = max(1, 1-dungeon[m-1][n-1])

    for i := m - 2; i >= 0; i-- {
        dp[i][n-1] = max(1, dp[i+1][n-1]-dungeon[i][n-1])
    }
    for j := n - 2; j >= 0; j-- {
        dp[m-1][j] = max(1, dp[m-1][j+1]-dungeon[m-1][j])
    }

    for i := m - 2; i >= 0; i-- {
        for j := n - 2; j >= 0; j-- {
            need := min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
            dp[i][j] = max(1, need)
        }
    }

    return dp[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);

        for (int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; --j) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, need);
            }
        }

        return dp[0][0];
    }
};

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

        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1])

        for i in range(m - 2, -1, -1):
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1])

        for j in range(n - 2, -1, -1):
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j])

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

        return dp[0][0]

var calculateMinimumHP = function(dungeon) {
  const m = dungeon.length;
  const n = dungeon[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));

  dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

  for (let i = m - 2; i >= 0; i--) {
    dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
  }
  for (let j = n - 2; j >= 0; j--) {
    dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
  }

  for (let i = m - 2; i >= 0; i--) {
    for (let j = n - 2; j >= 0; j--) {
      const need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
      dp[i][j] = Math.max(1, need);
    }
  }

  return dp[0][0];
};

中文

题目概述

给定一个地下城网格，负数扣血、正数加血。骑士从左上走到右下（只能向右或向下），要求全过程生命值始终至少为 1，求最小初始生命值。

核心思路

正向推导很难，因为当前位置需要多少血取决于未来路径。倒序 DP 最自然：定义“进入当前格子前至少要有多少血”，保证能活到终点。

最优算法（逆向动态规划）

设 dp[i][j] 为进入 (i, j) 时所需最小生命值。
状态转移：need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
生命值至少为 1，所以 dp[i][j] = max(1, need)。
终点初始化：dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])。

复杂度分析

时间复杂度：O(mn)。
空间复杂度：O(mn)（可优化到 O(n)）。

常见陷阱

- 把状态定义成“当前剩余最大血量”，会导致转移混乱。
- 忘记对结果做 max(1, ...) 下限保护。
- 终点格子的初始化写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m][n];

        dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, need);
            }
        }

        return dp[0][0];
    }
}

func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    dp[m-1][n-1] = max(1, 1-dungeon[m-1][n-1])

    for i := m - 2; i >= 0; i-- {
        dp[i][n-1] = max(1, dp[i+1][n-1]-dungeon[i][n-1])
    }
    for j := n - 2; j >= 0; j-- {
        dp[m-1][j] = max(1, dp[m-1][j+1]-dungeon[m-1][j])
    }

    for i := m - 2; i >= 0; i-- {
        for j := n - 2; j >= 0; j-- {
            need := min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
            dp[i][j] = max(1, need)
        }
    }

    return dp[0][0]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);

        for (int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int j = n - 2; j >= 0; --j) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }

        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, need);
            }
        }

        return dp[0][0];
    }
};

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

        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1])

        for i in range(m - 2, -1, -1):
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1])

        for j in range(n - 2, -1, -1):
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j])

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

        return dp[0][0]

var calculateMinimumHP = function(dungeon) {
  const m = dungeon.length;
  const n = dungeon[0].length;
  const dp = Array.from({ length: m }, () => Array(n).fill(0));

  dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

  for (let i = m - 2; i >= 0; i--) {
    dp[i][n - 1] = Math.max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
  }
  for (let j = n - 2; j >= 0; j--) {
    dp[m - 1][j] = Math.max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
  }

  for (let i = m - 2; i >= 0; i--) {
    for (let j = n - 2; j >= 0; j--) {
      const need = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
      dp[i][j] = Math.max(1, need);
    }
  }

  return dp[0][0];
};