1. 项目概述从一道经典DP题说起最近在带学生刷《信息学奥赛一本通》的DP章节又碰到了这道“1288三角形最佳路径问题”。这题可以说是动态规划Dynamic Programming, DP的“Hello World”但别小看它很多同学第一次接触时都会被它那看似简单的“三角形”外表迷惑搞不清状态怎么定义递推顺序怎么走。我自己当年学DP也是从这类数字三角形问题入的门。今天我就结合这道题把数字三角形类问题的解题思路、代码实现细节以及那些容易踩的坑掰开揉碎了讲清楚。无论你是正在备赛的OIer还是刚开始学习算法的新手这篇文章都能帮你把这道题吃透并掌握背后通用的DP思考框架。简单来说这道题描述了一个由数字组成的三角形你从顶部出发每次可以向下或者向右下移动一步一直走到底部。你的目标是找到一条路径使得路径上经过的数字之和最大。题目输入就是三角形的层数和每层的数字输出就是这个最大的和。这本质上是一个多阶段决策最优解问题是学习DP最完美的起点。2. 核心思路拆解为什么是“倒着来”2.1 暴力搜索的困境与DP的引入刚拿到题最直接的想法可能是深度优先搜索DFS从顶点(1,1)开始尝试所有“向下”或“右下”的走法直到最底层然后回溯比较所有路径的和。对于一个层数为h的三角形路径总数是2^(h-1)级别。当h较大时比如题目常见范围到100这个计算量是天文数字必然超时。这就引出了DP的核心思想避免重复计算利用已解决的子问题来构建原问题的解。在这个三角形里一个点(i, j)第i行第j列往下走它的后续路径和只取决于它下面两个点(i1, j)和(i1, j1)的后续最优路径。如果我们能先知道下面这两个点的“最佳路径和”那么(i, j)的最佳路径和就是a[i][j] max(dp[i1][j], dp[i1][j1])。这里dp[i][j]就是我们定义的状态表示从点(i, j)出发走到最底层所能获得的最大路径和。2.2 状态定义与“自底向上”的递推为什么状态要这么定义因为这样定义符合“无后效性”——当前点的未来收益只取决于它后续的状态而与之前是怎么走到这个点的无关。这是DP能成立的关键。确定了状态接下来就是递推顺序。既然一个点的状态依赖于它正下方和右下方的点那么最自然的计算顺序就是从最底层开始逐层向上推导。这就是所谓的“自底向上” (Bottom-up)的递推方式。初始化最底层第h行的每个点(h, j)因为从这里出发就是它自己所以dp[h][j] a[h][j]。递推对于第i行i从h-1递减到1第j列j从1到i状态转移方程为dp[i][j] a[i][j] max(dp[i1][j], dp[i1][j1])这个方程的含义非常直观当前点的最佳出路是选择下面两个点中“未来收益”更大的那一条然后加上自己的价值。答案最终dp[1][1]就是从顶点出发的最佳路径和。注意有些教程或初学者喜欢用“自顶向下”的记忆化搜索Memoization这当然也是DP的一种实现方式递归缓存。但对于这类结构规整的题目自底向上的递推代码更简洁效率也略高没有递归开销更推荐作为标准解法掌握。2.3 空间优化技巧滚动数组我们开了一个dp[h1][h1]的二维数组。仔细观察递推公式计算第i行的dp值只用到第i1行的dp值。也就是说我们并不需要保留所有行的状态只需要保留“当前行”和“下一行”即可。这就是“滚动数组”优化。我们可以只用一个一维数组f[j]来替代二维dp。在计算过程中f[j]在某一时刻代表的是“下一行”即原先的dp[i1][j]的值。当我们从底向上计算时初始化f[1...h] a[h][1...h]最底层。对于i从h-1到 1对于j从 1 到if[j] a[i][j] max(f[j], f[j1])注意计算f[j]时等号右边的f[j]和f[j1]存储的还是上一轮i1行的结果而等号左边的f[j]将被更新为本轮i行的结果。由于我们是从左向右计算更新f[j]不会影响后面f[j1]的计算因为f[j1]需要的是旧的f[j1]和f[j2]。经过滚动数组优化空间复杂度从 O(h²) 降到了 O(h)。这在h很大时能有效节省内存。3. 代码实现与逐行解析理解了思路我们来看C代码实现。我会给出两个版本标准二维DP版和优化后的滚动数组版并加上详细注释。3.1 标准二维DP版本#include iostream #include algorithm using namespace std; const int N 110; // 根据题目最大范围定义稍大一些避免边界问题 int a[N][N]; // 存储输入的数字三角形 int dp[N][N]; // dp[i][j]: 从(i,j)走到最底层的最大路径和 int main() { int h; cin h; // 1. 读入数据注意三角形是从第1行到第h行第i行有i个数 for (int i 1; i h; i) { for (int j 1; j i; j) { cin a[i][j]; } } // 2. 初始化最底层的dp值就是它自身的值 for (int j 1; j h; j) { dp[h][j] a[h][j]; } // 3. 自底向上递推 for (int i h - 1; i 1; i--) { // 从倒数第二行开始向上 for (int j 1; j i; j) { // 第i行有i个元素 // 状态转移方程当前点值 下方两个点中更好的未来 dp[i][j] a[i][j] max(dp[i 1][j], dp[i 1][j 1]); } } // 4. 输出结果顶点(1,1)的dp值即为答案 cout dp[1][1] endl; return 0; }代码要点解析数组下标从1开始这是处理这类矩阵/三角形问题的常见技巧可以避免很多边界判断比如i-1,j-1可能越界让代码更清晰。a[1][1]就是三角形的顶点。循环边界外层循环i从h-1递减到1内层循环j从1到i严格对应三角形的形状。max函数来自algorithm头文件用于比较两个值的大小。3.2 空间优化滚动数组版本#include iostream #include algorithm using namespace std; const int N 110; int a[N][N]; int f[N]; // 一维滚动数组初始代表“下一行”的dp值 int main() { int h; cin h; for (int i 1; i h; i) { for (int j 1; j i; j) { cin a[i][j]; } } // 初始化f数组存储最底层第h行的值 for (int j 1; j h; j) { f[j] a[h][j]; } // 自底向上递推使用滚动数组 for (int i h - 1; i 1; i--) { for (int j 1; j i; j) { // 关键用f[j]和f[j1]旧值更新f[j]新值 // 等号右边的f[j], f[j1]是上一轮(i1行)的结果 // 等号左边的f[j]将被更新为本轮(i行)的结果 f[j] a[i][j] max(f[j], f[j1]); // 注意计算完f[j]后原来的f[j]旧值就不需要了 // 而f[j1]在计算下一个f[j1]时需要的是它自己旧的值和f[j2]的旧值 // 由于我们是j从小到大计算f[j1]在未被覆盖前保存的正是我们需要的旧值 } // 当第i行计算完毕后f[1..i]存储的就是第i行的dp值 // 第i1行及之后的数据存在f[i1..h]在本轮及后续计算中不再需要 } // 最终f[1]存储的就是顶点(1,1)的dp值 cout f[1] endl; return 0; }滚动数组版本的核心理解很多同学对f[j] a[i][j] max(f[j], f[j1])感到困惑担心覆盖问题。我们画个内存图来理解 假设h4我们已经初始化f [x, a4,1, a4,2, a4,3, a4,4]下标从1开始x表示无用值。 现在计算i3行计算j1:f[1] a3,1 max(f[1], f[2])。f[1]被更新为dp[3][1]f[2]还是a4,2。计算j2:f[2] a3,2 max(f[2], f[3])。注意此时等号右边的f[2]是a4,2旧值f[3]是a4,3旧值。计算后f[2]被更新为dp[3][2]。计算j3:f[3] a3,3 max(f[3], f[4])。等号右边的f[3]是a4,3旧值f[4]是a4,4旧值。计算后f[3]被更新为dp[3][3]。 可以看到在计算过程中我们总是用尚未被覆盖的“旧值”即上一行的结果来生成“新值”当前行的结果并且计算顺序保证了不会发生冲突。这是滚动数组能正确工作的关键。4. 常见问题与实战调试技巧在实际做题和教学中我发现同学们容易在以下几个地方出错。4.1 输入输出与数组边界问题1读入数据时数组越界。这是最常见的问题之一。题目说第i行有i个数如果你用从0开始的索引循环要写成for (int j0; ji; j)或for (int j0; ji; j)容易搞混。强烈建议使用从1开始的索引这样i同时表示行号和该行元素个数循环写为for (int j1; ji; j)非常直观。问题2输出错误。有些同学递推完了直接输出a[1][1]或者dp[h][1]。一定要清楚你的状态定义是什么。在我们的定义下答案是dp[1][1]。如果是滚动数组版本答案是f[1]。调试技巧对于样例输入可以在递推完成后把整个dp数组或每轮计算后的f数组打印出来与手工计算的结果对比能快速定位逻辑错误。4.2 递推顺序与状态转移问题3递推顺序写反。如果错误地写成自顶向下i从1到h状态转移方程就需要写成dp[i][j] a[i][j] max(dp[i-1][j-1], dp[i-1][j])并且需要处理j1或ji的边界情况因为上一行可能没有j-1或j列。这比自底向上要麻烦。除非题目要求输出具体路径这时自顶向下更方便记录前驱否则统一用自底向上更简单可靠。问题4状态转移方程写错。最典型的错误是把max(dp[i1][j], dp[i1][j1])写成max(dp[i1][j], dp[i1][j])或者max(dp[i][j1], dp[i1][j])。一定要在纸上画一个小的三角形比如3层标出(i,j)、(i1,j)、(i1,j1)这几个位置加深印象。4.3 路径记录与输出原题只要求输出最大和。但很多类似的变种题或教学会要求输出这条最大路径本身。这里补充一下做法。我们需要在递推过程中记录每个状态(i,j)是从哪个决策转移过来的是来自(i1, j)还是(i1, j1)。通常用一个pre数组或path数组来存储。修改后的二维DP代码含路径记录#include iostream #include algorithm using namespace std; const int N 110; int a[N][N]; int dp[N][N]; int pre[N][N]; // pre[i][j] 记录从(i,j)出发下一步最优是走向列j还是j1这里用0表示向下(j)1表示向右下(j1) int main() { int h; cin h; for (int i 1; i h; i) for (int j 1; j i; j) cin a[i][j]; // 初始化底层 for (int j 1; j h; j) { dp[h][j] a[h][j]; // 最底层没有下一步pre可以不用管或设为-1 } // 自底向上递推并记录决策 for (int i h - 1; i 1; i--) { for (int j 1; j i; j) { int down dp[i 1][j]; // 向下的未来收益 int rightDown dp[i 1][j 1]; // 向右下的未来收益 if (down rightDown) { dp[i][j] a[i][j] down; pre[i][j] 0; // 选择向下走列号不变 } else { dp[i][j] a[i][j] rightDown; pre[i][j] 1; // 选择向右下走列号1 } } } cout 最大路径和为: dp[1][1] endl; // 输出路径从顶点开始根据pre数组回溯 cout 路径为: ; int curRow 1, curCol 1; cout a[curRow][curCol]; // 输出起点 while (curRow h) { if (pre[curRow][curCol] 0) { // 向下走 curRow; // curCol 不变 } else { // 向右下走 curRow; curCol; } cout - a[curRow][curCol]; } cout endl; return 0; }注意记录路径会增加空间开销多一个pre数组和时间开销回溯输出。如果题目只要求和就不要记录路径以节省资源。另外如果存在多条路径和相同上述代码会输出优先选择“向下”的那一条因为判断条件是down rightDown。如果题目有其他要求如输出字典序最小的路径则需要调整决策的优先级。4.4 数据范围与类型选择问题5忽略数据范围和整数溢出。题目没有明确给出数字的大小但根据经验这类题目数字可能比较大多个累加后可能超出int范围。一个良好的习惯是在竞赛中除非确定数据很小否则对于求和、累加类问题直接使用long long类型来定义dp数组和结果。将上面代码中的dp数组和f数组改为long long类型是更稳妥的做法。long long dp[N][N]; // 或者 long long f[N];5. 举一反三变种题型与思维扩展掌握了基础的数字三角形我们可以看看它的几种常见变种这能帮你真正理解DP的灵活性。5.1 变种一最小路径和这太简单了只需把状态转移方程中的max改为min即可。dp[i][j] a[i][j] min(dp[i1][j], dp[i1][j1])。初始化同理。5.2 变种二方向变化自顶向下定义有些题目或教材喜欢用另一种状态定义dp[i][j]表示从顶点(1,1)走到点(i,j)的最大路径和。此时递推方向是自顶向下初始化dp[1][1] a[1][1]状态转移dp[i][j] a[i][j] max(dp[i-1][j-1], dp[i-1][j])注意边界当j1最左边时只有dp[i-1][j]当ji最右边时只有dp[i-1][j-1]。答案max(dp[h][1], dp[h][2], ..., dp[h][h])最底层的最大值。这种定义在需要输出路径时更方便因为我们可以从终点反向推到起点。但递推时需要处理边界稍微麻烦一点。5.3 变种三多维度限制例如“三角形最佳路径问题”可能增加一个限制路径上经过的数字之和模K最大。这时状态就需要增加一维变成dp[i][j][r]表示走到(i,j)时路径和模K等于r是否可能布尔型或者能达到的最大实际和。这引入了“模”这个维度是DP中常见的“加维”思想。5.4 变种四矩阵中的路径问题摘花生问题这是一个非常经典的扩展在一个n*m的矩阵中从左上角(1,1)走到右下角(n,m)每次只能向右或向下走每个格子有花生数求能摘到的最大花生数。这其实就是数字三角形的“矩形版”状态定义为dp[i][j]表示走到(i,j)的最大值转移方程为dp[i][j] a[i][j] max(dp[i-1][j], dp[i][j-1])。理解了三角形这类问题就迎刃而解。6. 算法复杂度分析与适用场景最后我们来分析一下这个算法的效率并看看它适合解决什么样的问题。时间复杂度无论是标准二维DP还是滚动数组DP我们都需要遍历三角形中的每一个数字一次并进行一次常数时间的比较和加法操作。对于一个h层的三角形数字总数为12...h h*(h1)/2因此时间复杂度是O(h²)。这相比指数级的暴力搜索O(2^h)是巨大的优化。空间复杂度标准二维DP需要O(h²)的数组空间。滚动数组优化仅需O(h)的空间。适用场景最优子结构问题的最优解包含其子问题的最优解。在这道题里从(i,j)出发的最优路径必然包含从它下方两个点出发的后续最优路径之一。无后效性当前的决策只影响未来不影响过去。一旦(i,j)的dp值确定它之后怎么走就与之前如何到达(i,j)无关。多阶段决策问题可以分解为一系列前后关联的阶段。当你遇到一个问题感觉可以一步步做决策并且当前的选择会影响未来的结果同时未来的最优选择与过去无关时就应该考虑动态规划。数字三角形是培养这种思维直觉的绝佳训练场。我自己在初学DP时花了大量时间在纸上画三角形手动模拟递推过程直到对“状态”、“决策”、“转移”这些概念有了肌肉记忆。建议你也多做几次这样的练习用不同的状态定义去解同一道题比较它们的异同。当你看到一道新题能主动去思考“它的状态是什么怎么转移”那就说明你已经入门了。这道“三角形最佳路径问题”的代码虽然短但它蕴含的DP思想是许多复杂问题的基石值得反复咀嚼。