用二维数组存放入数字三角形,从顶部即a[1,1]开始,每个结点(如a[i,j])可以选择向下走到达a[i+1, j],或向右下走到达a[i+1,j+1],求一从顶部a[1,1]开始到底部(即数组的最后一行)一条路径,使该路径经过数字总和最大。显然,用动态规划可以自下而上求解,用tri[i,j]表示结点[i,j]到底部路径的最大数字总和,则问题的解为tri[1, 1],解结构为:
例如对于如下实例
7
5 6
8 7 4
3 10 9 2
例如tri[3,1] = 8 + max{3,10} = 18; tri[3,2] = 7 + max{10,9} = 17;设计该问题的动态规划算法(可用伪代码表示),并给出上述实例的解tri[1, 1]和路径。