0120. Triangle
==============
题目信息
--------
:题号: 0120. 三角形最小路径和
:难度: Medium
:主题: 动态规划、路径枚举、后缀状态、滚动数组
:原题: `LeetCode 0120 `_
:重点: 从二叉选择的完整路径搜索,合并重复的坐标状态,再按依赖方向自底向上压缩为一行
题目重述
--------
给定一个整数三角形 ``triangle``,路径从顶点 ``triangle[0][0]`` 开始。位于第 ``row`` 行第 ``column``
列时,下一步只能进入下一行的 ``column`` 或 ``column + 1``,路径必须一直到达最后一行。返回所有合法路径
中最小的节点值总和。
三角形行数在 ``1..200`` 范围内,第 ``i`` 行恰有 ``i + 1`` 个元素,每个值在 ``-10^4..10^4`` 范围内。
进阶目标是使用与行数成正比的额外空间;主解不修改输入。
自建示例
--------
* 含负数:``triangle = [[4],[2,9],[7,1,3],[8,6,-5,2]]``,返回 ``2``,最优路径为
``4 -> 2 -> 1 -> -5``;
* 局部贪心失败:``triangle = [[0],[1,2],[100,100,-100]]``,返回 ``-98``。第二行较小的 ``1`` 并不在
最优路径上;
* 单元素:``triangle = [[-7]]``,返回 ``-7``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int enumeratePaths(const std::vector>& triangle, int row, int column) {
if (row == static_cast(triangle.size()) - 1) {
return triangle[row][column];
}
const int sameColumn = enumeratePaths(triangle, row + 1, column);
const int nextColumn = enumeratePaths(triangle, row + 1, column + 1);
return triangle[row][column] + std::min(sameColumn, nextColumn);
}
int bottomUpTable(std::vector> best) {
for (int row = static_cast(best.size()) - 2; row >= 0; --row) {
for (int column = 0; column <= row; ++column) {
best[row][column] += std::min(best[row + 1][column], best[row + 1][column + 1]);
}
}
return best[0][0];
}
int bottomUpRolling(const std::vector>& triangle) {
std::vector best = triangle.back();
for (int row = static_cast(triangle.size()) - 2; row >= 0; --row) {
for (int column = 0; column <= row; ++column) {
best[column] = triangle[row][column] + std::min(best[column], best[column + 1]);
}
}
return best[0];
}
public:
int minimumTotal(std::vector>& triangle) {
return bottomUpRolling(triangle);
}
};
题解
----
完整路径搜索
~~~~~~~~~~~~
除最后一行外,每个位置都有两个合法后继,因此最直接的正确方案是递归尝试两侧,分别得到从两个孩子到底部
的最小路径和,再选择较小者。``enumeratePaths`` 覆盖每一步的全部选择组合,到达底行时返回终点值,所以
不会漏掉任何合法路径。
不能只比较下一行两个孩子的当前值。局部贪心示例在第二行会选择 ``1``,但它后面只能接 ``100``;选择当前
更大的 ``2`` 却能接 ``-100``,完整路径更小。正确比较对象是“从孩子到底部的最优后缀总和”,不是孩子
自身。
重复坐标状态
~~~~~~~~~~~~
递归搜索中,不同上方路径会汇合到同一坐标。例如 ``(row, column)`` 可以由上一行的 ``column - 1`` 或
``column`` 到达;一旦站在这个位置,后续最小代价只由当前位置决定,与之前怎样到达无关。
定义后缀状态:
.. code-block:: text
best(row, column) =
从 (row, column) 出发到底行的最小路径和
最后一行已经是终点:
.. code-block:: text
best(last, column) = triangle[last][column]
其他位置只有两个后继:
.. code-block:: text
best(row, column) = triangle[row][column]
+ min(best(row + 1, column),
best(row + 1, column + 1))
把每个坐标结果保存一次,原先指数级搜索树中汇合后的重复分支就被删除。
自底向上填表
~~~~~~~~~~~~
状态依赖下一行,所以从底行向上计算时,两个孩子结果都已经完成。``bottomUpTable`` 复制整个三角形作为
``best`` 表:底行无需修改,每个更高位置覆盖为自己的最优后缀代价,最终唯一顶点 ``best[0][0]`` 覆盖
所有合法路径。
负数不需要特殊处理。转移比较的是两个已经包含全部后续代价的状态,没有依据当前值正负剪枝;普通加法与
最小值仍保持最优子结构。
滚动一行
~~~~~~~~
计算第 ``row`` 行只读取第 ``row + 1`` 行,完整二维表中的更低历史行不会再次使用。``bottomUpRolling``
把工作数组初始化为底行,处理某行后,前 ``row + 1`` 个位置覆盖为该行状态。
更新按列从左向右进行。计算 ``best[column]`` 时,同列旧值在赋值前读取,右邻 ``best[column + 1]`` 尚未在
本轮覆盖,两者都属于下一行。若从右向左,右邻会先变成当前行状态,依赖层次就会混合。
对第一个示例:
.. list-table::
:header-rows: 1
* - 处理阶段
- 工作数组有效前缀
- 关键计算
* - 初始底行
- ``[8,6,-5,2]``
- 底行直接作为后缀代价
* - 合并 ``[7,1,3]``
- ``[13,-4,-2]``
- ``1 + min(6,-5) = -4``
* - 合并 ``[2,9]``
- ``[-2,5]``
- ``2 + min(13,-4) = -2``
* - 合并 ``[4]``
- ``[2]``
- ``4 + min(-2,5) = 2``
数组后方已失效位置无需清空,下一轮只读取仍属于有效下一行的相邻位置。
主解与复杂度
~~~~~~~~~~~~
公开入口采用一维自底向上 DP。它保留后缀状态的直接含义,把二维表中不会再使用的各行删除,同时通过复制
底行避免修改调用者的 ``triangle``。若允许覆盖输入,可直接在原三角形上执行同一转移,额外空间降为常数,
但会改变参数内容。
设行数为 ``r``,三角形共有 ``Θ(r²)`` 个位置。二维与滚动 DP 都对每个位置做常数工作,时间 ``Θ(r²)``;
二维副本空间 ``Θ(r²)``,滚动数组空间 ``O(r)``。裸递归会重复坐标状态,最坏为指数时间。