动态规划解决数塔问题_本关任务:编写用动态规划解决数塔问题。 相关知识 为了完成本关任务,你需要掌握:

这是完整的程序，可以直接运行。数塔模型在下面，也是测试数据。数塔图片如图所示，所谓的数塔问题就是，从上到下找到一条路径，使得经过的点的值加起来和最大，输出路径

#include <iostream>
using namespace std;
 
void main(){
	
	int d1[6][6],d2[6][6];
	int max,result;
	for (int i=1;i<=5;i++)
		for (int j=1;j<=i;j++)
		{
			cin>>d1[i][j];
			d2[i][j]=d1[i][j];
			
		}
		//构造数组d2
		int s=1;
		for(int x=5;x>=2;x--)
		{
			for (int y=1;y<=5-s;y++)
			{
				if(d2[x][y]>=d2[x][y+1])
					max=d2[x][y];
				else max=d2[x][y+1];
				
				//cout<<"max="<<max<<endl;
				d2[x-1][y]=max+d2[x-1][y];
			}
			s++;
		}
 
		//输出b2中的数据
		/*for (int i1=1;i1<=5;i1++)
		{
			for (int j1=1;j1<=i1;j1++)
			{
				cout<<d2[i1][j1]<<" ";	
			}
			cout<<endl;
		}*/
			
		//m横坐标，n纵坐标
		int m=1,n=1;
		
		cout<<"最大值的行走路径为："<<endl;
		//输出第一个路径
		cout<<d1[1][1]<<"  ";
 
		for(int a=1;a<=5;a++)
		{
			result=d2[m][n]-d1[m][n];
			if (result==d2[m+1][n])
			{
				m=m+1;//m的值每次都要向后移动一位
				cout<<d1[m][n]<<"  ";
			}
			else if(result==d2[m+1][n+1])
			{
				m=m+1;//m的值每次都要向后移动一位
				n=n+1;//n的值向后移动一位
				cout<<d1[m][n]<<"  ";
				
			}
		}
		cout<<endl;
}
 
/*
测试数据
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
*/