174. 地下城游戏
题目描述
地牢是一个 m x n 网格 dungeon。骑士从左上角出发，公主在右下角。骑士每一步只能向右或向下走一格。
每进入一个格子，骑士的生命值就加上该格的数值：负数表示被恶魔扣血，0 表示空房间，正数表示补血。起点和终点格子也照样生效。
骑士的初始生命值是正整数。只要某一时刻生命值不大于 0，骑士就立刻死亡。返回骑士能活着到达公主所在格子所需的最小初始生命值。
示例 1
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出：7
解释：沿 右、右、下、下 走，经过 -2、-3、3、1、-5。初始为 7 时生命值依次为 5、2、5、6、1，始终为正。
示例 2
输入：dungeon = [[0]] 输出：1
解释：格子值为 0，但初始生命值至少要是 1。
数据范围
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
解题思路：从右下到左上的动态规划
从起点往后推不行：前面剩多少血和后面需要多少血互相牵制。反过来从终点往回推：dp[i][j] 表示走进 (i,j) 之前至少要有的血量。从这里出发只能去右边或下边，选所需血量较小的那个，再减去本格的增减值；结果至少为 1，因为血量任何时候都要为正。
为什么正确
dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])，它只依赖右边和下边已经算好的格子。
复杂度分析
时间 O(mn)，空间 O(mn)（可压缩到 O(n)）。
易错点
从左上角正推并记录“最大剩余血量”是错的；另外别忘了 max(1, ...)，补血再多也不能让所需血量低于 1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
dp = [[math.inf] * (n + 1) for _ in range(m + 1)]
dp[m][n - 1] = dp[m - 1][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -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]class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[m][n - 1] = dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; 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];
}
}class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[m][n - 1] = dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; 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];
}
};func calculateMinimumHP(dungeon [][]int) int {
m, n := len(dungeon), len(dungeon[0])
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
for j := range dp[i] {
dp[i][j] = math.MaxInt32
}
}
dp[m][n-1], dp[m-1][n] = 1, 1
for i := m - 1; i >= 0; i-- {
for j := n - 1; 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]
}var calculateMinimumHP = function(dungeon) {
const m = dungeon.length, n = dungeon[0].length;
const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(Infinity));
dp[m][n - 1] = dp[m - 1][n] = 1;
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; 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];
};function calculateMinimumHP(dungeon: number[][]): number {
const m = dungeon.length, n = dungeon[0].length;
const dp: number[][] = Array.from({length: m + 1}, () => new Array(n + 1).fill(Infinity));
dp[m][n - 1] = dp[m - 1][n] = 1;
for (let i = m - 1; i >= 0; i--) {
for (let j = n - 1; 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];
}其他解法
正向时路径上有两个互相影响的量（初始生命值和当前生命值），二分答案先固定其中一个；反向动态规划直接定义“从这里出发至少需要多少生命”，只用一次 O(mn) 就得到答案。
解法 2：二分答案 + 正向动态规划 时间 O(mn·log C)，空间 O(mn)
初始生命值越大越容易通关，具有单调性，可以二分初始生命值 h。给定 h 后，从左上角正向做动态规划：best[i][j] 表示走到 (i,j) 时能保留的最大生命值，由上方和左方中仍大于 0 的较大者加上当前格子得到，结果不大于 0 则不可达。右下角可达就说明 h 足够。C 是答案的取值上界。
固定 h 后“保留最大生命值”具有最优子结构，正向动态规划变得可行，帮助理解为什么不固定 h 时正向做不通。代价是多一个 log C 因子。
from typing import List
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
def ok(h):
best = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
prev = h
else:
prev = max(best[i - 1][j] if i > 0 else 0,
best[i][j - 1] if j > 0 else 0)
if prev > 0 and prev + dungeon[i][j] > 0:
best[i][j] = prev + dungeon[i][j]
return best[m - 1][n - 1] > 0
lo, hi = 1, 1
while not ok(hi):
hi *= 2
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return loclass Solution {
private boolean ok(int[][] d, long h) {
int m = d.length, n = d[0].length;
long[][] best = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long prev;
if (i == 0 && j == 0) prev = h;
else prev = Math.max(i > 0 ? best[i - 1][j] : 0, j > 0 ? best[i][j - 1] : 0);
if (prev > 0 && prev + d[i][j] > 0) best[i][j] = prev + d[i][j];
}
}
return best[m - 1][n - 1] > 0;
}
public int calculateMinimumHP(int[][] dungeon) {
long lo = 1, hi = 1;
while (!ok(dungeon, hi)) hi *= 2;
while (lo < hi) {
long mid = (lo + hi) / 2;
if (ok(dungeon, mid)) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}
}class Solution {
bool ok(vector<vector<int>>& d, long long h) {
int m = d.size(), n = d[0].size();
vector<vector<long long>> best(m, vector<long long>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long long prev;
if (i == 0 && j == 0) prev = h;
else prev = max(i > 0 ? best[i - 1][j] : 0LL, j > 0 ? best[i][j - 1] : 0LL);
if (prev > 0 && prev + d[i][j] > 0) best[i][j] = prev + d[i][j];
}
}
return best[m - 1][n - 1] > 0;
}
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
long long lo = 1, hi = 1;
while (!ok(dungeon, hi)) hi *= 2;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (ok(dungeon, mid)) hi = mid;
else lo = mid + 1;
}
return (int)lo;
}
};func calculateMinimumHP(dungeon [][]int) int {
m, n := len(dungeon), len(dungeon[0])
ok := func(h int) bool {
best := make([][]int, m)
for i := range best {
best[i] = make([]int, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
prev := 0
if i == 0 && j == 0 {
prev = h
} else {
if i > 0 {
prev = max(prev, best[i-1][j])
}
if j > 0 {
prev = max(prev, best[i][j-1])
}
}
if prev > 0 && prev+dungeon[i][j] > 0 {
best[i][j] = prev + dungeon[i][j]
}
}
}
return best[m-1][n-1] > 0
}
lo, hi := 1, 1
for !ok(hi) {
hi *= 2
}
for lo < hi {
mid := (lo + hi) / 2
if ok(mid) {
hi = mid
} else {
lo = mid + 1
}
}
return lo
}var calculateMinimumHP = function(dungeon) {
const m = dungeon.length, n = dungeon[0].length;
const ok = (h) => {
const best = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let prev;
if (i === 0 && j === 0) prev = h;
else prev = Math.max(i > 0 ? best[i - 1][j] : 0, j > 0 ? best[i][j - 1] : 0);
if (prev > 0 && prev + dungeon[i][j] > 0) best[i][j] = prev + dungeon[i][j];
}
}
return best[m - 1][n - 1] > 0;
};
let lo = 1, hi = 1;
while (!ok(hi)) hi *= 2;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (ok(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
};function calculateMinimumHP(dungeon: number[][]): number {
const m = dungeon.length, n = dungeon[0].length;
const ok = (h: number): boolean => {
const best: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let prev: number;
if (i === 0 && j === 0) prev = h;
else prev = Math.max(i > 0 ? best[i - 1][j] : 0, j > 0 ? best[i][j - 1] : 0);
if (prev > 0 && prev + dungeon[i][j] > 0) best[i][j] = prev + dungeon[i][j];
}
}
return best[m - 1][n - 1] > 0;
};
let lo = 1, hi = 1;
while (!ok(hi)) hi *= 2;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (ok(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
};