用动态规划法求总和最大的路径问题如下（求详细程序代码）1、问题描述有形如下图所示的数塔（每行的整数比上一行多一个）,从顶部出发,每一步的走法要么是选择向下走,要么是向右下

Question

用动态规划法求总和最大的路径 问题如下（求详细程序代码）
1、问题描述
有形如下图所示的数塔（每行的整数比上一行多一个）,从顶部出发,每一步的走法要么是选择向下走,要么是向右下走.比如：从第三行第二个数60,要么向下走到18,要么向右下走到29.这样一直走到底层.要求找出一条路径,使路径上的数的总和最小.要求用动态规划法求解.
9
12 15
10 60 18
23 18 29 45
19 71 10 84 16
要求：
输入：第一行是一个整数N(1

Answer 1

令f[i][j]表示从第i行第j个数走到底所能得到的最小和,则有：
f[i][j]=min(f[i+1][j],f[i+1][j+1])+a[i][j],式中a[i][j]为第i行第j个数的值,最后一行f[i][j]=a[i][j],则f[1][1]即为答案