前言

数字三角形是一道经典的动态规划（dynamic programming, DP）入门题：给定一个由数字组成的三角形，从顶部出发，每次只能走到下一行相邻的两个位置之一，求到达底部时路径上数字之和的最大值。它的规模不大，暴力枚举所有路径也能做，但路径数量随层数指数增长，层数稍多就跑不动。DP 的价值在于把「指数级的路径枚举」压缩成「每层每个位置一个最优值」。

最常见的误解是「自顶向下递推时，每个位置只保留最大值就够了」。这在求和问题上成立，因为加法满足最优子结构：到达某位置的最大和，等于该位置的值加上到达其上方两个父位置的最大和中的较大者。但如果题目改成「求和的最小值」或者「记录路径」，状态定义与转移就要跟着变，不能照搬。

另一个误解是忽略负数的存在。很多数字三角形的样例全是正数，于是有人把「最优值」初始化成 0，遇到全负的输入就得到错误答案。本文分别给出自顶向下与自底向上两种写法，并说明空间优化与路径还原的处理方式。

一、状态定义与转移方程

把三角形存成二维数组a[i][j]，其中0 <= j <= i < n。定义dp[i][j]为「从顶部走到第 i 行第 j 列时，能获得的最大和」。由于每一步只能从左上(i-1, j-1)或正上(i-1, j)过来，转移方程是：

dp[i][j] = a[i][j] + max(dp[i-1][j-1], dp[i-1][j])

边界要单独处理：最左列j == 0只能从正上方来，最右列j == i只能从左上方来，顶点dp[0][0] = a[0][0]。最终答案是最后一行的最大值，而不是dp[n-1][n-1]——终点可以是底部的任意一列。

这套定义的时间复杂度是 O(n²)，空间复杂度也是 O(n²)。由于每一行的状态只依赖上一行，空间可以压缩到 O(n)：从右往左更新一维数组，避免覆盖还未使用的值。

二、自底向上：更简洁的写法

自底向上的思路是反过来定义状态：dp[j]表示「从第 i 行第 j 列出发，走到最底部能得到的最大和」。转移变成：

dp[j] = a[i][j] + max(dp[j], dp[j+1])

这里dp[j]是下一行同列的值，dp[j+1]是下一行右邻列的值。初值是最后一行的元素本身。因为每次只用到下一行，一维数组就够，而且不需要处理左右边界的特判——j的范围是0..i，j+1最大取到i+1，恰好是下一行的有效下标。

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

long long max_path_sum(const std::vector<std::vector<int>>& tri) {
if (tri.empty()) {
return 0;
}
std::vector<long long> dp(tri.back().begin(), tri.back().end());

for (int i = static_cast<int>(tri.size()) - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[static_cast<std::size_t>(j)] =
static_cast<long long>(tri[static_cast<std::size_t>(i)]
[static_cast<std::size_t>(j)]) +
std::max(dp[static_cast<std::size_t>(j)],
dp[static_cast<std::size_t>(j) + 1]);
}
}
return dp[0];
}

这段代码有几个点需要核对。i用int并从size() - 2开始，是因为size()是std::size_t，直接减 2 在空三角或只有一行时会下溢；函数开头已经处理了空输入，但「只有一行」时size() - 2仍然会回绕，所以先转成int再减。dp用long long，是因为路径和可能超出int范围，而有符号整数溢出是未定义行为（undefined behavior, UB），不是简单的「变成负数」。

tri.back()复制到dp时，std::vector<long long>的迭代器范围构造会把每个int转成long long，这是合法的隐式转换。若三角形为空，tri.back()是 UB，所以必须先判断empty()。

三、完整示例与路径还原

如果只需要最大值，上面的函数就够了。如果还需要输出具体路径，就得额外记录「每个位置是从左边还是上边来的」。一种做法是再开一个n × n的char表，存 0 表示从左上来、1 表示从正上来；另一种做法是在自底向上时记录每步选择了哪一侧。

// 适用于 C++17
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
std::vector<std::vector<int>> tri = {
{7},
{3, 8},
{8, 1, 0},
{2, 7, 4, 4},
{4, 5, 2, 6, 5}
};

const int n = static_cast<int>(tri.size());
// best[i][j]：从 (i, j) 到底部的最大和
std::vector<std::vector<long long>> best(
static_cast<std::size_t>(n),
std::vector<long long>(static_cast<std::size_t>(n), 0));

for (int j = 0; j < n; ++j) {
best[static_cast<std::size_t>(n - 1)]
[static_cast<std::size_t>(j)] =
tri[static_cast<std::size_t>(n - 1)]
[static_cast<std::size_t>(j)];
}

for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
best[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] =
tri[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)] +
std::max(best[static_cast<std::size_t>(i + 1)]
[static_cast<std::size_t>(j)],
best[static_cast<std::size_t>(i + 1)]
[static_cast<std::size_t>(j) + 1]);
}
}

std::cout << "max sum: " << best[0][0] << '\n';

int j = 0;
for (int i = 0; i < n; ++i) {
std::cout << tri[static_cast<std::size_t>(i)]
[static_cast<std::size_t>(j)];
if (i + 1 < n) {
const long long left =
best[static_cast<std::size_t>(i + 1)]
[static_cast<std::size_t>(j)];
const long long right =
best[static_cast<std::size_t>(i + 1)]
[static_cast<std::size_t>(j) + 1];
std::cout << " -> ";
if (right > left) {
++j;
}
}
}
std::cout << '\n';
return 0;
}

路径还原的关键是：站在(i, j)时，比较下一行(i+1, j)与(i+1, j+1)的best值，谁大就往谁走。若两者相等，走哪边都能得到同样的最大和，代码里固定走左边（right > left才右移），保证输出确定。打印箭头与选路判断分开写，避免把「输出什么」和「走到哪」混在同一个表达式里。

用样例手工推演：底部是4 5 2 6 5；倒数第二行2 7 4 4对应2+max(4,5)=7、7+max(5,2)=12、4+max(2,6)=10、4+max(6,5)=10；继续向上，最终顶点值应当是 30，路径为7 -> 3 -> 8 -> 7 -> 5。这个结果可以逐层核对，用来检查实现对不对。

四、复杂度与变体

几个常见变体值得注意。若把「最大」改成「最小」，转移里的max换成min，但初始化不能用 0，要用足够大的哨兵值或直接以底行为初值。若允许从底部任意位置出发、到顶部结束，把三角形上下翻转即可。若移动规则改成「可以走到下一行任意列」，问题就退化成「每行取最大值再求和」，不再需要 DP。若数字范围很大，路径和要用long long，甚至在数值超过 64 位时改用高精度。

还有一个容易忽略的点：三角形的存储不一定要用vector<vector<int>>。用一维数组按行优先展开，a[i * (i + 1) / 2 + j]定位，缓存局部性更好，内存分配次数也更少。对于竞赛类输入，这种写法很常见；对于可读性优先的业务代码，二维结构更清楚。

常见坑点

坑点一：把答案取成最后一行的最后一个元素。

❌return dp[n - 1][n - 1];，终点可以是底部任意一列。

✅ 对最后一行取最大值，或在自底向上写法中直接返回dp[0]。

坑点二：自顶向下时不处理左右边界。

❌ 统一写max(dp[i-1][j-1], dp[i-1][j])，最左列访问dp[i-1][-1]越界。

✅ 最左列只取正上方，最右列只取左上方，或把数组整体右移一列留出哨兵。

坑点三：用 0 初始化最优值。

❌ 全负数三角形时，max结果被 0 拉高，得到错误答案。

✅ 用底行元素本身作为初值，或用负无穷哨兵。

坑点四：路径和用int累加。

❌ 层数多、数值大时溢出，属于 UB。

✅ 用long long保存dp值，输入转换时显式提升。

坑点五：size() - 2在短输入上下溢。

❌for (std::size_t i = tri.size() - 2; i >= 0; --i)，空或单行时回绕成巨大值。

✅ 先转int，并在函数开头处理空输入。

坑点六：还原路径时只看当前层，不看子问题的值。

❌ 比较a[i+1][j]与a[i+1][j+1]的大小来决定走向。

✅ 比较best[i+1][j]与best[i+1][j+1]，即两条子路径的最优值。

坑点七：认为 DP 一定比暴力快。

❌ 在 n 只有 5 时也套一层二维表，代码更长且没有实际收益。

✅ 理解 DP 的收益来自消除重叠子问题，规模极小时暴力反而更简单。

总结

数字三角形的 DP 之所以经典，是因为它把「最优子结构」和「重叠子问题」两件事同时展示了出来：每个位置的最优值只由下一层的两个位置决定，而这两个位置又被上层大量复用。把状态定义从「从顶部到此处」换成「从此处到底部」，边界处理立刻简化，这也是解题时值得先想一想的切入点。