数字金字塔（动态规划输出路径）

男娘i 2022-06-08 05:44 259阅读 0赞

### 【题目描述】 ###

观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。

![1284.gif][]

在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。

### 【输入】 ###

第一个行包含R(1<= R<=1000)，表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

所有的被供应的整数是非负的且不大于100。

### 【输出】 ###

单独的一行，包含那个可能得到的最大的和。

### 【输入样例】 ###

5
    13
    11 8
    12 7  26
    6  14 15 8
    12 7  13 24 11

### 【输出样例】 ###

13->8->26->15->24

### 【来源】 ###

![20170916180701591][]

#include<iostream>
    #include<cstring>
    #define MAXN 1000
    using namespace std;
    int a[MAXN+10][MAXN+10][4];
    //a[x][y][1]存储本身的数值；
    //a[x][y][2]存储最大值;
    //a[x][y][3]存储前进的方向，0往下，1往右 
    int main()
    {
    	memset(a,0,sizeof(a));
    	int n,x,y;
    	cin>>n;
     	for(int x=1;x<=n;x++)
     	{
     		for(int y=1;y<=x;y++)
     		{
     			cin>>a[x][y][1];
     			a[x][y][2]=a[x][y][1];//初始状态 
     			a[x][y][3]=0;
     		}
     	}
     	for(x=n-1;x>=1;x--) 
     	{
     		for(y=1;y<=x;y++)
     		{
     			if(a[x+1][y][2]>a[x+1][y+1][2])//选择路径，保留最大路径值 
     			{
     				a[x][y][2]=a[x][y][1]+a[x+1][y][2];
     				a[x][y][3]=0;
     			}
     			else
     			{
     				a[x][y][2]=a[x][y][1]+a[x+1][y+1][2];
    				a[x][y][3]=1; 
     			}
     		}
     	}
     	cout<<a[1][1][2]<<endl;
     	y=1;
     	for(x=1;x<=n-1;x++)//输出最大值的路径 
     	{
     		cout<<a[x][y][1]<<"->";
     		y=y+a[x][y][3];
     	}
     	cout<<a[x][y][1]<<endl;
    }

[1284.gif]: /images/20220608/00b693052f454056ab3084fb02882bdf.png
[20170916180701591]: /images/20220608/5b48e3792cd94b40b186aba4bea098a4.png