A61468. $有正实数构成的数字三角形排列形式如图所示。第一行的数为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的路径上的\dots$

单选题

知识点

动态规划二维数组数字三角形状态转移方程

题目描述

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

mac{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]}+ ai,j

上一题下一题