单选题

由正实数构成的数字三角形排列如图所示,第一行为数字 a1,1,第二行的数从左到右依次为 a2,1、 a2,2,第 n 行的数为 an,1、an,2...an,n。从 a1,1 开始,每一行的数ai,j 只有两条边可以分别通向下一行的两个数 ai+1,j 和 ai+1,j+1。用动态规划算法找出一条从 a1,1 向下通到 an,1、 an,2...an,n 中的某个路径,是的该路径上的数之和最大。

令 C[i][j]是从 a1,1 到 ai,j 的路径上的数值,并且 C[i][0] = C[0][j] = 0,则 C[i][j] = ( )

A

max(C[i−1][j−1],C[i−1][j])+ai,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])+ai,j

赣ICP备20007335号-2