💻 三角形取数(Hard Version)
华为 · 动态规划 · 算法编程题
华为
动态规划
n ≤ 300
时限 1 秒 / 256 MB
题目描述
给定一个由 n 行构成的数字三角形。第 i 行共有 2i-1 个整数，整体形状如下图所示（以 n=3 为例）：
从顶点（第一行唯一的数字）出发，依次向下移动恰好 n-1 次直到抵达最后一行。 假设当前位于第 i 行第 j 列： _1. 可以向正下方移动至第 (i+1) 行第 j 列； _2. 可以向左下方移动至第 (i+1) 行第 (j-1) 列； _3. 可以向右下方移动至第 (i+1) 行第 (j+1) 列。 每到达一个位置都会获得该位置的数值。定义在整个行走过程中，向左下方移动的次数记为 l ，向右下方移动的次数记为 r 。我们需要满足 |l-r|≤ k 请你选择一条合法路径，使得获得数值之和最大，并输出该最大值。
输入输出
输入描述
在一行上输入两个整数 n,k(1≤ n≤ 300;0≤ k≤ n) ，分别表示数字三角形的行数与允许的移动差。 此后 n 行，第 i 行输入 2i-1 个整数 a_i,1,a_i,2,... ,a_i,2i-1(-2×10^9≤ a_i,j≤ 2×10^9) 共计 Σ_i=1^n(2i-1)=n^2 个整数。
输出描述
输出一个整数，表示满足条件的路径可以取得的最大数值之和。
样例共 2 组
样例 1 · 在该样例中，可选取的最大路径为
第 1 行：取 1 ；
第 2 行：向右下方移动，取 4 ；
第 3 行：向正下方移动，取 8 。
总和为 1+4+8=13 ，且 |l-r|=1≤ 1 。
输入
3 1 1 2 3 4 5 6 7 8 9
输出
13
样例 2
输入
3 0 1 2 3 4 5 6 7 8 9
输出
12
算法解析依据充分
考点：动态规划
数据规模 n ≤ 300 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：n ≤ 300
- 元素值域：a_i ≤ 2000000000，j ≤ 2000000000（注意整数类型选择，避免溢出）
- 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
推荐方向：动态规划
本题切入点
数字三角形上加了 |l−r| ≤ k 的约束（向左下、向右下的次数差有界）：状态用 dp[i][j][d] 表示「到第 i 行第 j 列、向左比向右多走 d 步」的最大和，逐行转移后取 |d| ≤ k 的最优值；n≤300 时可用滚动数组或按可达状态压缩。
把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。
思路框架（动态规划 通法 · 非本题专属）
- 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
- 写转移方程：当前状态由哪些更小的状态推来。
- 确定初始条件与遍历顺序（保证用到的状态已算好）。
- 确定答案取哪个状态；数值大时全程取模。
实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。
复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)
该范式的通法易错点
- 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
- 初始化写错（尤其「恰好」与「至多」的初值差别）。
- 遍历顺序与依赖方向不一致。
对照本题
- 数据规模 n ≤ 300，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
- 元素值域最大到 2000000000 —— 求和 / 相乘时记得开 64 位整数。
样例解读
样例 1：输入 3 1 / 1 / 2 3 4 / 5 6 7 8 9 → 输出 13
在该样例中，可选取的最大路径为
第 1 行：取 1 ；
第 2 行：向右下方移动，取 4 ；
第 3 行：向正下方移动，取 8 。
总和为 1+4+8=13 ，且 |l-r|=1≤ 1 。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：华为机试编程模拟题4。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解