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}=$（   ）。

选项

• A. $\max\{C_{i-1,j-1}, C_{i-1,j}\} + a_{i,j}$
• B. $C_{i-1,j-1} + C_{i-1,j}$
• C. $\max\{C_{i-1,j-1}, C_{i-1,j}\} + 1$
• D. $\max\{C_{i,j-1},C_{i-1,j}\} + a_{i,j}$

答案

A

题解

考点定位

本题考「数字三角形 DP」,对应大纲 4.3.2（难度【2】）。

解题过程

C[i][j] = max(C[i−1][j−1], C[i−1][j]) + a[i][j]。

选 A。

易错提醒

① 与 2019 年同型；② 前驱来自上一行两侧。