CSP-S 2019 第一轮 第15题：有正实数构成的数字三角形排列形式如图所示。第一行的数为α1,1；第二行

题目

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

题解

选 A： \[ \boxed{C[i][j]=\max\{C[i-1][j-1],C[i-1][j]\}+a_{i,j}} \]

关键是看：到达 \(a_{i,j}\) 的前一步在哪里？

根据题目的走法，只可能从上一行的两个位置过来：

• \(a_{i-1,j-1}\)：此前的最大路径和是 \(C[i-1][j-1]\)；
• \(a_{i-1,j}\)：此前的最大路径和是 \(C[i-1][j]\)。

为了让总和最大，选择这两种路径中较大的一个，再加上当前位置的数 \(a_{i,j}\)，就得到选项 A。

注意：三角形两侧的点只有一个合法前驱，实现时应单独处理。起点为 \(C[1][1]=a_{1,1}\)，最后的答案是 \[ \max_{1\le j\le n} C[n][j]. \]