数字金字塔（动态规划）

曾经终败给现在 2022-06-08 04:44 205阅读 0赞

### 【例9.2】数字金字塔 ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 293 通过数: 191

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

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

![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

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

### 【来源】 ###

[No][]

![20170914215356473][]

逆推：

/*
    5
    13 
    11 8
    12 7 26
    6 14 15 8
    12 7 13 24 11
    */
    #include<iostream>
    #include<cstring>
    using namespace std;
    int f[1010][1010];//f[i][j]从第i行第j个数到最后一行的最大数字和 
    int a[1010][1010];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(f,0,sizeof(f));
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++)//初始状态 
    	{
    		f[n][i]=a[n][i];
    	}
    	for(int i=n;i>=1;i--)//i个阶段 
    	{
    		for(int j=1;j<=i;j++)//j个状态 
    		{
    			f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);//取两个方向的最大数字和 
    		}
    	}
    	cout<<f[1][1]<<endl;
    	return 0;
    }

顺推：

![20170914220220906][]

/*
    5
    13 
    11 8
    12 7 26
    6 14 15 8
    12 7 13 24 11
    */
    #include<iostream>
    #include<cstring>
    #define MAXN 1000
    using namespace std;
    int f[MAXN+10][MAXN+10];
    int a[MAXN+10][MAXN+10];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(f,0,sizeof(f));
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	f[1][1]=a[1][1];
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);
    		}
    	}
    	int maxn=0;
    	for(int i=1;i<=n;i++)
    	{
    		maxn=max(maxn,f[n][i]);
    	}
    	cout<<maxn<<endl;
    	return 0;
    }

空间优化：可以将二维数组降为一维数组。

![20170914222425787][]

/*
    5
    13 
    11 8
    12 7 26
    6 14 15 8
    12 7 13 24 11
    */
    #include<iostream>
    #include<cstring>
    #define MAXN 1000
    using namespace std;
    int a[MAXN+10][MAXN+10];
    int f[MAXN+10];
    int main()
    {
    	memset(a,0,sizeof(a));
    	memset(f,0,sizeof(f));
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    //	f=a[n];
        for(int i=1;i<=n;i++)
        {
        	f[i]=a[n][i];
        }
    	for(int i=n-1;i>=1;i--)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			f[j]=a[i][j]+max(f[j],f[j+1]);
    		}
    	}
    	cout<<f[1]<<endl;
    	return 0;
    }

用指针代替数组：

#include<iostream>
    #include<cstring>
    #define MAXN 1000
    using namespace std;
    int a[MAXN+10][MAXN+10];
    int *f;
    int main()
    {
    	memset(a,0,sizeof(a));
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	f=a[n];//指向第n行数据 
    	for(int i=n-1;i>=1;i--)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			f[j]=a[i][j]+max(f[j],f[j+1]);
    		}
    	}
    	cout<<f[1]<<endl;
    	return 0;
    }

[1284.gif]: /images/20220608/46f281c5b5e74237ae7e07343433e750.png
[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No
[20170914215356473]: /images/20220608/e70309f0c4494f46ac8a66746b54edd9.png
[20170914220220906]: /images/20220608/ea82ab617cd045fc9afe38f0a31b4314.png
[20170914222425787]: /images/20220608/c06cd40b63b74a52891b82b8ceb9bdd3.png