0174. Dungeon Game
==================
题目信息
--------
:题号: 0174. 地下城游戏
:难度: Hard
:主题: 动态规划、逆向状态、网格、空间压缩
:原题: `LeetCode 0174 `_
:重点: 从路径前缀生命约束逆推每格最低入场生命,再把二维后继需求压缩到一行
题目重述
--------
给定 ``m x n`` 整数网格 ``dungeon``。骑士从左上角进入,只能向右或向下移动,最终到达
右下角。进入格子后,生命立即加上该格的数值;生命在任何时刻都必须至少为 1,降到 0
或以下就会失败。
返回保证骑士能够到达终点所需的最小初始生命值。
自建示例
--------
.. code-block:: text
输入:
dungeon = [
[-2, -3, 3],
[-5,-10, 1],
[10, 30, -5]
]
输出:7
选择 -2 -> -3 -> 3 -> 1 -> -5,生命从 7 开始依次变为
5 -> 2 -> 5 -> 6 -> 1,全程存活。
.. code-block:: text
输入:dungeon = [[5]]
输出:1
即使格子增加生命,进入前也至少要有 1 点生命。
.. code-block:: text
输入:dungeon = [[-8]]
输出:9
进入后恰好剩 1 点生命。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
int twoDimensional(
const std::vector>& dungeon) {
int rows = static_cast(dungeon.size());
int columns = static_cast(dungeon[0].size());
long long unreachable =
std::numeric_limits::max() / 4;
std::vector> need(
rows + 1,
std::vector(columns + 1, unreachable));
need[rows][columns - 1] = 1;
need[rows - 1][columns] = 1;
for (int row = rows - 1; row >= 0; --row) {
for (int column = columns - 1; column >= 0; --column) {
long long next_need = std::min(
need[row + 1][column], need[row][column + 1]);
need[row][column] = std::max(
1LL,
next_need - dungeon[row][column]);
}
}
return static_cast(need[0][0]);
}
int rollingRow(
const std::vector>& dungeon) {
int rows = static_cast(dungeon.size());
int columns = static_cast(dungeon[0].size());
long long unreachable =
std::numeric_limits::max() / 4;
std::vector need(columns + 1, unreachable);
need[columns - 1] = 1;
for (int row = rows - 1; row >= 0; --row) {
for (int column = columns - 1; column >= 0; --column) {
long long next_need =
std::min(need[column], need[column + 1]);
need[column] = std::max(
1LL,
next_need - dungeon[row][column]);
}
}
return static_cast(need[0]);
}
public:
int calculateMinimumHP(
std::vector>& dungeon) {
return rollingRow(dungeon);
}
};
题解
----
枚举路径为什么迅速失控
~~~~~~~~~~~~~~~~~~~~~~
从起点到终点的每条路径都可以独立检查:累加沿途格子值,记录最小前缀和;若最小前缀为
``lowest``,这条路径所需初始生命就是 ``max(1, 1 - lowest)``。枚举全部路径后取最小值,
定义上完全正确。
瓶颈是同一个格子之后的剩余路径会被许多不同前缀反复枚举,路径数随行列组合呈指数级
增长。只最大化终点总和也不够:一条最终收益很高的路径可能先遭受致命伤害,生命约束作用
于每个前缀,而不只作用于终点。
从起点正向描述还会携带“当前生命、沿途最低生命、到达方式”等历史。题目真正提供的结构
是每个格子只有右、下两个后继;从终点反向看,未来要求可以被压缩成一个标量。
逆向状态删除路径历史
~~~~~~~~~~~~~~~~~~~~
定义 ``need[row][column]``:在进入格子 ``(row,column)`` **之前**,从该格走到终点并
始终存活所需的最小生命值。
设当前格效果为 ``effect``。若选择的后继要求入场生命 ``next_need``,当前入场生命
``health`` 必须同时满足:
.. code-block:: text
health >= 1
health + effect >= next_need
所以针对这个后继,最低入场生命是:
.. code-block:: text
max(1, next_need - effect)
骑士可以在向右、向下中选择需求较小的后继。上述公式关于 ``next_need`` 单调不减,
因此转移为:
.. code-block:: text
next_need = min(need[row + 1][column], need[row][column + 1])
need[row][column] = max(1, next_need - dungeon[row][column])
这个状态不再区分有多少条前缀到达当前格,也不枚举后续路径;每个子网格只保留完成它所需
的最低入场资源。
为何必须从终点向起点扫描
~~~~~~~~~~~~~~~~~~~~~~~~~~
当前状态依赖右侧与下方两个后继,所以计算顺序必须保证它们已经确定:行从下到上、列从
右到左。右下角没有真实后继,可以把“完成任务后仍活着”视为需求 1 的虚拟后继,于是
同一公式得到:
.. code-block:: text
need[last] = max(1, 1 - dungeon[last])
这同时解释单格正数答案为何仍为 1,以及单格 ``-8`` 为何需要 9。
二维状态与边界哨兵
~~~~~~~~~~~~~~~~~~
``twoDimensional`` 在真实网格下方和右侧增加一圈不可达大值,只把右下角下方、右下角
右方两个虚拟位置设为 1。右下角因而能选择需求 1;底行其他格的下方仍不可达,只能选择
已计算的右侧;最右列其他格同理只能选择真实下方。
不能把整条虚拟边界都设为 1,否则算法会错误允许骑士从任意底行格向下离开,或从任意
最右列格向右离开。不可达哨兵的意义是保持“只能走向网格内合法后继”。
二维表的具体走读
~~~~~~~~~~~~~~~~
标准示例从右下向左上计算出的最低入场生命为:
.. code-block:: text
need = [
[7, 5, 2],
[6, 11, 5],
[1, 1, 6]
]
右下角值为 -5,完成后至少剩 1,因此入场需要 6。它左侧的 30 能把生命补到足够水平,
所以入场只需 1。中间的 -10 可以选择需求为 1 的下方格,故需要
``max(1, 1 - (-10)) = 11``。
起点的两个后继需求分别是 5、6,选择较小的右侧;经过起点 -2 前需要
``max(1, 5 - (-2)) = 7``。沿所选路径,进入每个下一格时都恰好满足表中的需求。
一维数组如何保留依赖
~~~~~~~~~~~~~~~~~~~~
计算当前行时只需要“下一行”和“当前行右侧”,完整二维历史不再有用。``rollingRow``
把状态压缩到长度 ``columns + 1`` 的数组:
* 更新 ``need[column]`` 前,它保存下方格的需求;
* 因为列从右向左扫描,``need[column + 1]`` 已更新为当前行右侧格的需求;
* 写回后,``need[column]`` 成为当前格需求,供左侧格和上一行继续使用。
数组初始全是不可达大值,仅 ``need[columns - 1] = 1``,表示右下角下方的唯一虚拟后继;
最右端 ``need[columns]`` 始终保持不可达。每个真实格在逆序中至少有一个有限后继,所以
取最小值后不会拿不可达哨兵参与减法。
正确性与方案选择
~~~~~~~~~~~~~~~~
对逆向顺序归纳:右下角的虚拟需求正确;若右、下状态都表示各自最小入场生命,转移选择
需求更小的合法后继,并计算足以承受当前格效果且至少为 1 的最小生命,因此当前状态既不
低估也不高估。归纳到左上角,``need[0][0]`` 正是最小初始生命。
二维方案直接对应状态定义,时间 ``O(mn)``、空间 ``O(mn)``;一维方案不改变转移,只
删除不会再被读取的旧行,时间仍为 ``O(mn)``,额外空间降为 ``O(n)``,因此主解采用
``rollingRow``。状态和减法使用 ``long long``,避免哨兵或累积伤害在中间计算中溢出;
题目保证最终答案适合接口的 ``int`` 返回类型。