C++数字三角形问题与dp算法

前言数字三角形是一道经典的动态规划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[j1])这里dp[j]是下一行同列的值dp[j1]是下一行右邻列的值。初值是最后一行的元素本身。因为每次只用到下一行一维数组就够而且不需要处理左右边界的特判——j的范围是0..ij1最大取到i1恰好是下一行的有效下标。// 适用于 C17#include algorithm#include cstddef#include iostream#include vectorlong long max_path_sum(const std::vectorstd::vectorint tri) {if (tri.empty()) {return 0;}std::vectorlong long dp(tri.back().begin(), tri.back().end());for (int i static_castint(tri.size()) - 2; i 0; --i) {for (int j 0; j i; j) {dp[static_caststd::size_t(j)] static_castlong long(tri[static_caststd::size_t(i)][static_caststd::size_t(j)]) std::max(dp[static_caststd::size_t(j)],dp[static_caststd::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::vectorlong long的迭代器范围构造会把每个int转成long long这是合法的隐式转换。若三角形为空tri.back()是 UB所以必须先判断empty()。三、完整示例与路径还原如果只需要最大值上面的函数就够了。如果还需要输出具体路径就得额外记录「每个位置是从左边还是上边来的」。一种做法是再开一个n × n的char表存 0 表示从左上来、1 表示从正上来另一种做法是在自底向上时记录每步选择了哪一侧。// 适用于 C17#include algorithm#include cstddef#include iostream#include vectorint main() {std::vectorstd::vectorint tri {{7},{3, 8},{8, 1, 0},{2, 7, 4, 4},{4, 5, 2, 6, 5}};const int n static_castint(tri.size());// best[i][j]从 (i, j) 到底部的最大和std::vectorstd::vectorlong long best(static_caststd::size_t(n),std::vectorlong long(static_caststd::size_t(n), 0));for (int j 0; j n; j) {best[static_caststd::size_t(n - 1)][static_caststd::size_t(j)] tri[static_caststd::size_t(n - 1)][static_caststd::size_t(j)];}for (int i n - 2; i 0; --i) {for (int j 0; j i; j) {best[static_caststd::size_t(i)][static_caststd::size_t(j)] tri[static_caststd::size_t(i)][static_caststd::size_t(j)] std::max(best[static_caststd::size_t(i 1)][static_caststd::size_t(j)],best[static_caststd::size_t(i 1)][static_caststd::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_caststd::size_t(i)][static_caststd::size_t(j)];if (i 1 n) {const long long left best[static_caststd::size_t(i 1)][static_caststd::size_t(j)];const long long right best[static_caststd::size_t(i 1)][static_caststd::size_t(j) 1];std::cout - ;if (right left) {j;}}}std::cout \n;return 0;}路径还原的关键是站在(i, j)时比较下一行(i1, j)与(i1, j1)的best值谁大就往谁走。若两者相等走哪边都能得到同样的最大和代码里固定走左边right left才右移保证输出确定。打印箭头与选路判断分开写避免把「输出什么」和「走到哪」混在同一个表达式里。用样例手工推演底部是4 5 2 6 5倒数第二行2 7 4 4对应2max(4,5)7、7max(5,2)12、4max(2,6)10、4max(6,5)10继续向上最终顶点值应当是 30路径为7 - 3 - 8 - 7 - 5。这个结果可以逐层核对用来检查实现对不对。四、复杂度与变体写法时间空间特点暴力枚举所有路径O(2ⁿ)O(n) 递归栈只适合极小规模自顶向下 记忆化O(n²)O(n²)思路直观需处理边界自底向上二维O(n²)O(n²)便于还原路径自底向上一维O(n²)O(n)只求值时的最优选择几个常见变体值得注意。若把「最大」改成「最小」转移里的max换成min但初始化不能用 0要用足够大的哨兵值或直接以底行为初值。若允许从底部任意位置出发、到顶部结束把三角形上下翻转即可。若移动规则改成「可以走到下一行任意列」问题就退化成「每行取最大值再求和」不再需要 DP。若数字范围很大路径和要用long long甚至在数值超过 64 位时改用高精度。还有一个容易忽略的点三角形的存储不一定要用vectorvectorint。用一维数组按行优先展开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[i1][j]与a[i1][j1]的大小来决定走向。✅ 比较best[i1][j]与best[i1][j1]即两条子路径的最优值。坑点七认为 DP 一定比暴力快。❌ 在 n 只有 5 时也套一层二维表代码更长且没有实际收益。✅ 理解 DP 的收益来自消除重叠子问题规模极小时暴力反而更简单。总结要点结论状态从某位置出发到底部的最大和转移当前值加下方两个子问题中的较大者方向自底向上无需边界特判空间一维数组滚动O(n)路径还原记录选择或反查子问题的值数值用long long防溢出数字三角形的 DP 之所以经典是因为它把「最优子结构」和「重叠子问题」两件事同时展示了出来每个位置的最优值只由下一层的两个位置决定而这两个位置又被上层大量复用。把状态定义从「从顶部到此处」换成「从此处到底部」边界处理立刻简化这也是解题时值得先想一想的切入点。