一本通1258题解

**由于体验课问题,计划向后推几天😉**

题目

原链接

【题目描述】

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

TOWER

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

【输入】

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

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

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

【输出】

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

【输入样例】

1
2
3
4
5
6
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

【输出样例】

1
86

解题思路

深搜

因为只有左右,条件便于判断,so
直接尝试每种情况,通过不断的尝试得出最佳答案。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>


using namespace std;

int a[1001][1001],ans=0,n;

void dfs(int x,int y,int now)
{
if (x==n)
{
if (now>ans) ans=now;
return ;
}
dfs(x+1,y,now+a[x+1][y]);
dfs(x+1,y+1,now+a[x+1][y+1]);
}

int main()
{
int i,j;
cin>>n;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
cin>>a[i][j];
dfs(1,1,a[1][1]);
cout << ans;
return 0;
}

然后见证奇迹的时刻

TLE

TLE!!!好!不亏是动态规划!

还是太慢了

那么

优化版深搜

上一个方法有严重的问题,当n比较大时会花费太多时间,因为它进行了重复的搜索。因此,我们需要重新定义递归函数dfs。定义dfs(int x,int y)表示(x,y)到终点的最大权值和,最后的答案就是dfs(1,1)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
int a[1010][1010],book[1010][1010];
int n;
int dfs(int x,int y)
{
if(book[x][y]==-1)
{
if(x==n) book[x][y]=a[x][y];
else book[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
}
return book[x][y];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
cin>>a[i][j];
book[i][j]=-1;
}
dfs(1,1);
cout<<book[1][1]<<endl;
return 0;
}

然后就OK了

小总结

动态规划即为多阶段决策过程的最优化问题
其实就是合适的加一些条件,不断优化,每道题都有不同的优化方式,总之要因题制宜。

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