动态规划：三角形楼塔的最远路程_如下图所示的数字三角形

如下图所示的数字三角形。假设某个人从该三角形的顶部出发，在每一个结点处均可选择向左走或者向右走，一直走到底层。试设计一个算法，帮助该人从顶部走到底部，使其所走的所有数字之和最大。

输入要求：输入第1行为数字三角形元素的个数N，第2行为N个整数，分别表示按行输入的数字三角形的每一个元素的值。
输出要求：输出占1行，1个整数，表示该人从最顶部走到底部所有数字之和的最大值。
输入样例：
15
9 12 15 10 6 8 2 18 9 5 19 7 10 4 16
输出样例：
59
一个动态规划题目，分析如下
用二维数组存放各个方块的数字:
第一层第一个数a[1][1]=9,第二层第一个数a[2][1]=12,第二层第二个数a[2][2]=15,第三层第一个数a[3][1]=10…
一共五层，第一层到第五层得最大值=第一层的值+第二层到第五层的最大值
第二层到第五层的最大值=第二层的值+第三层到第五层的最大值
第三层到第五层的最大值=第三层的值+第四层到第五层的最大值
a[i][j]=a[i][j]+max{a[i+1][j],a[i+1][j+1]}
最终最大值为a[1][1]

#include<iostream>
using namespace std;
int a[100][100];
void main()
{
	int N,i,j,k,row;
	cin>>N;
	for(i=1,k=0;k<N;i++)
		for(j=1;j<=i;j++)
		{
			cin>>a[i][j];
			k++;
		}
		row=i-1;//row为行数
/*		cout<<row;
		for(i=1;i<=row;i++)//此处可以输出a[i][j]数组
		{
			for(j=1;j<=i;j++)
				cout<<a[i][j]<<" ";
			cout<<endl;
		}
		*/
		for(i=row-1;i>0;i--)
			for(j=1;j<=i;j++)
				a[i][j]=a[i][j]+(a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1]);
		cout<<a[1][1]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

算法：
日后再补