递推算法之数塔问题

如图所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。

1、一步可沿左斜线向下或右斜线向下走；
2、三角形行数小于等于100；
3、三角形中的数字为0,1，...，99；

测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

我的代码：

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int main()
{
	int numbers[101][101],i,j,n;
	cout<<"请输入层数：";
	cin>>n;	//输入层数 
	
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=i;++j)
		{
			cin>>numbers[i][j];	//输入每一层的值 
		}
	}
	
	
	for (i=n-1;i>=1;--i)
	{
		for (j=1;j<=i;++j)
		{
			if (numbers[i+1][j]>=numbers[i+1][j+1])
			{
				numbers[i][j]+=numbers[i+1][j];
			}
			else
			{
				numbers[i][j]+=numbers[i+1][j+1];
			}
		 } 
	}
	cout<<endl<<"最大路径和：";
	cout<<numbers[1][1]<<endl;	//输出最终结果 
	
	return 0; 
}

我的大体思路：
从上往下看，每2层要运算一次，因此，大循环只需循环n（层数）-1次。
从左往右看，每一次大循环中每2层中的下一层的x个数字，每个数字要相互比较一次，选出较大的数与上一层对应的一个数相加，因此每一层的数字之间需比较x-1次。

所以n是5层，那么大循环只需n-1次，又因为最后一层中（第n层），有n（5）个数字，那么每2个数字只需比较n-1次，也就是4次。
如：第5层中的第1个元素和第2个元素相比较，选较大的与第4层的第1个元素相加（第1次比较）；第2个元素和第3个元素相比较，选较大的与第4层的第2个元素相加（第2次比较）；第3个元素和第4个元素相比较，选较大的与第4层的第3个元素相加（第3次比较）；第4个元素和第5个元素相比较，选较大的与第4层的第4个元素相加（第4次比较）。

最后按规律递推。

最终结果：