P1216 [IOI 1994 / USACO1.5] 数字三角形 题解复盘
P1216 [IOI 1994 / USACO1.5] 数字三角形 题解复盘
模块：动态规划
类型：路径DP
目标：求从三角形顶部到底部的最大路径和
基本信息
| 项目 | 内容 |
|---|---|
| 题目编号、来源 | P1216 IOI 1994 / USACO1.5 |
| 训练层级 | 普及 |
| 知识版块 | 路径DP、二维DP、状态转移 |
解题前・关键信号识别
| 维度 | 分析 |
|---|---|
| 目标、约束、底层结构 | 从三角形顶部走到底部，每一步只能走到左下或右下，求路径和最大。属于典型路径DP。 |
| 数据规模 | r≤1000，可以使用 O(n²) 的动态规划。 |
| 候选算法和依据 | 暴力枚举所有路径，复杂度 O(2^n)，无法通过。 使用动态规划，每个位置只计算一次。 |
| 复杂度预判 | 时间复杂度：O(n²) 空间复杂度：O(n²) |
解题后・外化复盘
| 维度 | 内容 |
|---|---|
| 状态定义 | 定义：dp[i][j]表示：从顶点走到第 i 行第 j 个位置时能够获得的最大路径和。 |
| 状态转移 | 左边界：dp[i][1]=dp[i-1][1]+a[i][1]右边界： dp[i][i]=dp[i-1][i-1]+a[i][i]中间位置： dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j] |
| 遍历顺序 | 从上往下逐层计算，每一层依赖上一层，因此按行递增遍历。 |
| 实现结构 / 核心思路 | 1. 输入数字三角形。 2. 初始化 dp[1][1]。3. 按行进行状态转移。 4. 最后一层所有位置中取最大值作为答案。 |
| 错因回溯 | 第一次提交数组开成105×105，数据范围为r≤1000，导致数组越界 RE。之后改成1005×1005成功 AC。 |
| 边界和易错点 | 1. 第一列只能由正上方转移。 2. 最后一列只能由左上方转移。 3. 最终答案不是 dp[n][n]，而是最后一层的最大值。4. 注意数组大小要满足 r≤1000。 |
| 下次看到什么信号，我应该想到这个方法 | 看到： ① 网格/三角形路径问题 ② 每个位置只依赖上一层 ③ 求最优路径和 想到：路径DP（二维DP）。 |
AC完整代码
#include<iostream>#include<algorithm>usingnamespacestd;inta[1005][1005];intdp[1005][1005];intmain(){intn;cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){cin>>a[i][j];}}dp[1][1]=a[1][1];for(inti=2;i<=n;i++){for(intj=1;j<=i;j++){if(j==1){dp[i][j]=dp[i-1][j]+a[i][j];}elseif(j==i){dp[i][j]=dp[i-1][j-1]+a[i][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];}}}intans=0;for(inti=1;i<=n;i++){ans=max(ans,dp[n][i]);}cout<<ans;return0;}总结
| 项目 | 内容 |
|---|---|
| 类型 | 路径DP |
| 状态 | dp[i][j]：到达(i,j)的最大路径和 |
| 转移 | 从左上或右上转移 |
| 边界 | 第一列、最后一列单独处理 |
| 遍历顺序 | 从上到下、从左到右 |
| 最终答案 | 最后一层所有状态中的最大值 |
记忆
路径DP 状态： dp[i][j] = 到达(i,j)的最优值 转移： 由能够到达当前位置的状态转移 边界： 无法同时拥有两个来源的位置单独处理 答案： 最后一层（或终点）取最优