树塔.cpp

这是学习动态规划时用动态规划设计分析实际问题

#include"iostream"
using namespace std;
void main()
{
	int a[100][100];
	int b[100][100]={0};
	int n,i,j;
	 cout<<"输入数塔层数n:";
	cin>>n;cout<<endl;

	for(i=0;i<n;i++)
		for(j=0;j<=i;j++)
			cin>>a[i][j];
		

  cout<<"此数塔为:"<<endl;
	{   for(i=0;i<n;i++)
      {
		   for(j=0;j<=i;j++)
			 {   
				cout<<" ";
				cout<<a[i][j];
			 }
				cout<<endl;
		}
	}
	for(i=0;i<n;i++)
		b[n-1][i]=a[n-1][i];

	for( i=n-2;i>=0;i--)
		for( j=0;j<=n-1;j++)
		{
			if(b[i+1][j]>b[i+1][j+1])
				b[i][j]=a[i][j]+b[i+1][j];
			else 
				b[i][j]=a[i][j]+b[i+1][j+1];
		}
		cout<<"此数塔路径的最大值:"<<b[0][0]<<endl;
	cout<<"此数塔最大值的路径为:";
	 j=0;
		for(i=0;i<n;i++)
		{
			if(b[i][j]>b[i][j+1])
				j=j;
			else
				j=j+1;
			cout<<a[i][j]<<"->";
			
		}
	cout<<"和最大值"<<b[0][0]<<endl;
	cout<<endl;
}