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

{{ select(1) }}

• $\max\{C[i-1][j-1],C[i-1][j]\}+a_{i,j}$
• $C[i-1][j-1]+C[i-1][j]$
• $\max\{C[i-1][j-1],C[i-1][j]\}+1$
• $\max\{C[i][j-1],C[i-1][j]\}+a_{i,j}$