一：题目描述
给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输入
输入时第一行一个整数n，表示该数塔的行数，其余n行表示该塔每行的数值 输出
输出包含两行，第一行为最大路径上的数值之和， 第二行n个数字为从上而下最大路径数值 样例输入 5 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 样例输出 59 9 12 10 18 10
二 : 问题分析 用二维数组存放数塔。 D（i，j）表示第i行第j个数字 Maxsum（r，j）表示从D（i，j）到底边的各条路径中，最大的那条
那么问题可简化为求Maxsum（1,1） 三: 算法分析 典型递归问题： D（r，j）出发，下一步只能走D（r+1，j）或D（r+1，j+1）。所以对于n行数塔 If（r==n） Maxsum(r,j)=D（r，j）； Else maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+a[i][j];
AC代码：
#include<cstdio> #include<cmath> using namespace std; int a[100][100]; int maxsum[100][100],dis[50]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++){ maxsum[n][i]=a[n][i]; } for(int i=n-1;i>=1;i--){ for(int j=1;j<=i;j++){ maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+a[i][j]; } } int a=1,b=1; for(int i=1;i<=n;i++){ if(maxsum[a+1][b]>maxsum[a+1][b+1]){ dis[i]=maxsum[a][b]-maxsum[a+1][b]; a=a+1;b=b; }else{ dis[i]=maxsum[a][b]-maxsum[a+1][b+1]; a=a+1;b=b+1; } } cout<<maxsum[1][1]<<endl; for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }