实数构成的数字三角形排列形式如图所示。
第一行的数为 (a_{1,1}),第二行的数从左到右依次为 (a_{2,1}, a_{2,2})。第 (n) 行的数为 (a_{n,1}, a_{n,2}, \ldots, 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}, \ldots, a_{n,n}) 中某个数的路径,使得该路径上的数之和最大。 令 (c[i][j]) 是从 (a_{1,1}) 到 (a_{i,j}) 的路径上的数的最大和,并且 (c[i][0] = c[0][j] = 0),则 (c[i][j] = )?
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]