CSP-S 提高级 · CSP 2019 提高级第一轮 第 15 题

正实数构成的数字三角形排列形式如图所示。第一行的数为 $a_{1,1}$；第二行的数从左到右依次为 $a_{2,1},a_{2,2}$，第 $n$ 行的数为$a_{n,1},a_{n,2},\dots,a_{n,n}$ 从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1},a_{n,2},\dots,a_{n,n}$ 中某个数的路径，使得该路径上的数之和最大。


令 $C[i][j]$ 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和，并且 $C[i][0]=C[0][j]=0$，则 $C[i][j]=$ ( )。

这题就是数字三角形求最大和，拿到题先想：到 a[i][j] 只能从上一行左上方 a[i-1][j-1] 或正上方 a[i-1][j] 下来，所以最优解肯定是这两条路径里和更大的那条，再加上当前格子的数 a[i][j] 即可。

最容易栽跟头的就是状态转移方向搞反，把“往下走”想成“往上走”，或者把 max 写成 sum 以为两条路都要算；还有很多人会忘记加上 a[i][j] 本身，只把上一行的结果拿来比较就选答案，导致算出来的值永远偏小；另外选项 D 里混进同一行的 C[i][j-1] 也是典型陷阱，因为题目明确说了只能向下走，同一行之间没有边。

Q15 数字三角形动态规划

考察知识点

• 动态规划基础
• 数字三角形（经典 DP 模型）
• 状态转移方程