题目描述
观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。
输入
第一个行包含R(1≤R≤1000)R(1≤R≤1000),表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
输出
单独的一行,包含那个可能得到的最大的和。
输入样例
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
输出样例
86
这是ybt里DP的第一题,可见其重要程度,DP嘛,一步一步来,还是很容易的
a[i][j]保存金字塔,用f[i][j]来表示到a[i][j]时的最大数字和
正推
(i,j)可以从(i-1,j)和(i-1,j-1)到来,所以f[i][j]自然就与f[i-1][j]和f[i-1][j-1]有关
要取最大值,那就是max(f[i-1][j],f[i-1][j-1])
还要加上当前(i,j)的数值,于是得出状态转移方程:
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
最后,由于不知道具体的路径(其实可以再开个数组存下,递归输出)ans存在f[n][j]中,这里1<=j<=n
初始状态
当开始推时,也就是i==j==1时,(i,j)是必经之路
也就是f[1][1]=a[1][1]
边界条件
由于涉及到f[i-1][j-1],所以i,j都要从1开始,f[i][0]=0
第i行只有i个数,所以f[i][j]=0,这里j>i
f[N][N]直接开全局变量不行吗
复杂度O(n^2)
/*
6545089840720070558
*/
#define define define
//正推
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N];
int f[N][N];
int n;
int main()
{
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];
int ans=-1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
for(int i=1;i<=n;i++)
if(f[n][i]>ans)
ans=f[n][i];
cout<<ans;
return 0;
}
既然可以倒推,那为什么不能正推呢?
依然用f[i][j]表示到(i,j)时的最大值
状态转移方程:f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
ans存在f[1][1]中
/*
6545089840720070558
*/
#define define define
//倒推
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],f[N][N];
int main()
{
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=n;i>=1;i--)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
cout<<f[1][1];
return 0;
}
再提供一种思路
没有讲解???
我太懒了
记忆化搜索(倒推)
/*
6545089840720070558
*/
#define define define
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N];
int f[N][N];
int n;
int dfs(int x,int y);
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
cout<<dfs(1,1);
return 0;
}
int dfs(int x,int y)
{
if(f[x][y])
return f[x][y];
if(x==n)
return a[x][y];
return f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
}