P1716题解

原题链接

题目描述

观察下面的数字金字塔。

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

1
2
3
4
5
         7 
3 8
8 1 0
2 7 4 4
4 5 2 6 5

在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大

输入格式

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

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

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

输出格式

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

解题思路

非常经典的动态规划

如果只是用简单的递归或者搜索 将会浪费较多的时间
因为 比如当你在这两个点做选择时,你都将会用到的数值,而每次都去求一次数值十分浪费时间,因为求的最大值还会不断的重复重复重复…
这时,使用记忆化搜索 将每个地方可以得到的最大值存下来将可以省很多的时间
当然也可以使用动态规划 转移方程式如下

1
dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>

using namespace std;

int a[1003][1003],dp[1003][1003];

int main()
{
int n,x,y;
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=i;j>=1;j--)
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
cout<<dp[1][1];
return 0;
}

-------------本文结束,感谢您的阅读-------------