正实数构成的数字三角形排列形式如图所示。第一行的数为
a1,1;第二行的数从左到右依次为
an,1,an,2,…,an,n从 a1,1开始,每一行的数 ai,j
只有两条边可以分别通向下一行的两个数 ai+1,j和 ai+1,j+1。用动态规划算法找出一条从 a 1,1向下通到 an,1,an,2,…,an,n 中某个数的路径,
使得该路径上的数之和最大。
令 C[i][j] 是从 a1,1到 ai,j 的路径上的数的最大和,并且 C[i][0]=C[0][j]=0,则 C[i][j]= ( )。
max{C[i−1][j−1],C[i−1][j]}+ai,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