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完整代码#includeiostream#includealgorithmusingnamespacestd;inta[1005][1005];intdp[1005][1005];intmain(){intn;cinn;for(inti1;in;i){for(intj1;ji;j){cina[i][j];}}dp[1][1]a[1][1];for(inti2;in;i){for(intj1;ji;j){if(j1){dp[i][j]dp[i-1][j]a[i][j];}elseif(ji){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];}}}intans0;for(inti1;in;i){ansmax(ans,dp[n][i]);}coutans;return0;}总结项目内容类型路径DP状态dp[i][j]到达(i,j)的最大路径和转移从左上或右上转移边界第一列、最后一列单独处理遍历顺序从上到下、从左到右最终答案最后一层所有状态中的最大值记忆路径DP 状态 dp[i][j] 到达(i,j)的最优值 转移 由能够到达当前位置的状态转移 边界 无法同时拥有两个来源的位置单独处理 答案 最后一层或终点取最优