AI题库 · 信息学奥赛-提高级题库
题目分享 #22528
有正实数构成的数字三角形排列形式如图所示。

第一行的数为a11;第二行的数从左到右依次为a21,a,22;…第n行的数为an1, an2,…. ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2.…,ann中某个数的路径,使得该路径上的数之和达到最大。
令C[i,j]是从a11到aij的路径上的数的最大和,并且C[i,0]=C[0,j]=0,则C[i,j]=( )。
A
max{C[i-1,j-1],C[i-1,j]}+ aij
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]}+ aij
AI题库 · 编程考级与信奥赛真题库
查看答案 →
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。