动态的数字三角形

试题描述

    一个数字组成的三角形，有n行，第i行有i个数。从第一个数开始，每次可以往左下或右下走一格，直到走到最后一行，把沿途经过的数全部加起来。如何走才能得到最大的和？
    举个例子：

    为了简单起见，输入时将每行的数依次输入，第一个数之前并不输入空格。

输入

第一行：n，表示这个三角形共有n行
第二至n+1行：依次为这个数字三角形各行的数据（按顺序输入），两数之间有一个空格分隔。

输出

一个数，表示最大的和

输入示例

4
1
3 2
4 10 1
4 3 2 20

输出示例

其他说明

xjr提示你：简单的dp，你懂的。数据范围：0 < n < 1001，组成数字三角形的数都是不超过1000的自然苏。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 int a[1001][1001],b[1001][1001];
 5 int read() //输入模板 
 6 {
 7     int x=0,f=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-') f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 } 
21 int main()
22 {
23     int n,i,j;
24     n=read();
25     for(i=1;i<=n;i++)
26         for(j=1;j<=i;j++) a[i][j]=read();
27     //for(i=1;i<n/2;i++) a[n/2][i]=0;
28     for(i=1;i<=n;i++)
29     {
30         for(j=1;j<=i;j++)
31         {
32             b[i][j]=max(a[i][j]+b[i-1][j-1],a[i][j]+b[i-1][j]);
33         }
34     }
35     int ans=0;
36     for(i=1;i<=n;i++)
37         if(b[n][i]>ans) ans=b[n][i];
38     printf("%d",ans); 
39     //system("pause");
40     return 0;
41 }

动态的数字三角形

具体思路见相册中的动态的数字三角形~