NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 13 题

有正实数构成的数字三角形排列形式如图所示。第一行的数为 $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}=$（ ）。 

这题本质是数字三角形DP，拿到题先想：走到当前格只能来自正上方或左上方，所以最优策略就是取这两条路里较大的那个加上当前数，直接套公式选A。

很多同学会忽略边界条件，以为C[i][0]和C[0][j]不用管，结果数组越界或者逻辑跑飞；还有人会把转移写成两个来源直接相加，忘了取max；更有甚者把加法换成加1，完全没理解题意是求路径和的最大值，这些坑都要避开。

考点概念：数字三角形DP

这题考的是经典的数字三角形动态规划。状态定义很简单：C[i][j] 表示从顶点 a[1][1] 走到第 i 行第 j 列这个位置时，所能获得的路径最大和。

命题视角：为什么这么考？

命题人特别喜欢在数字三角形里挖“转移方程”的坑。它看似简单，实则检验你是否真正理解了"最优子结构"：要走到 (i, j) 并让总和最大，你必须先从 (i-1, j-1) 或 (i-1, j) 这两个位置里挑一个总和更大的走下来，否则你前面多花的路径长度在当前位置就注定是浪费的。同时，题目特意给了边界条件 C[i][0]=C[0][j]=0，这是为了防止数组越界访问，也是很多学生容易忽略的细节。