问题描述
(图3.1-1)示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径,使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走;
●1<三角形行数≤100;
●三角形中的数字为整数0,1,…99;
输入格式
文件中首先读到的是三角形的行数。
接下来描述整个三角形
输出格式
最大总和(整数)
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
咱就是说,看到这个题目马上想到当前路径的值加到下一个路径的值,最后在取出最大的路径值就可以了。
方法简单粗暴,直接开始吧,首先来看看我的思路吧
以题目例子为例
7 | 0 | 0 | 0 | 0 |
3 | 8 | 0 | 0 | 0 |
8 | 1 | 0 | 0 | 0 |
2 | 7 | 4 | 4 | 0 |
4 | 5 | 2 | 6 | 5 |
未标红的都是数组初始化的值,可以不管。
第一步是7,走到第二步,变化如下
7 | 0 | 0 | 0 | 0 |
3+7=10 | 8+7=15 | 0 | 0 | 0 |
8 | 1 | 0 | 0 | 0 |
2 | 7 | 4 | 4 | 0 |
4 | 5 | 2 | 6 | 5 |
第三步则同理
7 | 0 | 0 | 0 | 0 |
10 | 15 | 0 | 0 | 0 |
8+10=18 | 1+max(10,15)=16 | 0+16=16 | 0 | 0 |
2 | 7 | 4 | 4 | 0 |
4 | 5 | 2 | 6 | 5 |
这里取max就是取当前路径步值最大的了,然后我们可以看到当前路径的首尾只能选一个,也就是j=1和j=i的情况,如上面中的8只能+10,0只能+16,而中间可以选两个,那么这个特殊判断一下就好了
以此类推,走完后,数值如下
7 | 0 | 0 | 0 | 0 |
10 | 15 | 0 | 0 | 0 |
18 | 16 | 15 | 0 | 0 |
20 | 25 | 20 | 19 | 0 |
24 | 30 | 27 | 26 | 24 |
如图所示,可以看到最大的就是那个30了
那么接下来看AC代码咯,一样的简单粗暴(有注释)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int n,x;
int d[105][105]={0};
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>d[i][j];
}
}
//正片开始
int qmax=d[1][1]; //初始化,也就是三角形的头部
for(int i=2;i<=n;i++){ //从第二行开始
for(int j=1;j<=i;j++){ //每列
if(j!=1&&j!=i){ //中间那一块可以选两个
d[i][j]+=max(d[i-1][j],d[i-1][j-1]);//加上大的那个
qmax=max(qmax,d[i][j]); //保证qmax是当前最大的
}
else{
if(j==1){ //每行的首情况
d[i][j]+=d[i-1][j];
qmax=max(qmax,d[i][j]); //这里也要保证qmax是最大的
}
else if(j==i){ //每行的尾情况
d[i][j]+=d[i-1][j-1];
qmax=max(qmax,d[i][j]); //这里也要保证qmax是最大的
}
}
}
}
cout<<qmax; //输出最大的qmax
}
上面的代码虽然已经能AC了,但咱们还是建议读者学习一下这个记忆化搜索。我们一步一步往下来呈现记忆化的过程。
上面AC的代码是按从顶往下的路径走法,可能复杂度为2^n次方,这个复杂度很不理想,虽然是暴力,但这个暴力还能在优化,优化后的复杂度可以为n^2。
我们首先来递推一下
如果按照从底向上的走法,那么就不需要考虑首尾的下标情况了,咱们直接看图
7 | 0 | 0 | 0 | 0 |
3 | 8 | 0 | 0 | 0 |
8 | 1 | 0 | 0 | 0 |
2(max(4,5)+2=7) | 7(max(5,2)+7=12) | 4(max(2,6)+4=10) | 4(max(6,5)+4=10) | 0 |
4(4) | 5(5) | 2(2) | 6(6) | 5(5) |
以此类推,最终变成
7(30) | 0 | 0 | 0 | 0 |
3(23) | 8(21) | 0 | 0 | 0 |
8(20) | 1(13) | 0(10) | 0 | 0 |
2(7) | 7(12) | 4(10) | 4(10) | 0 |
4(5) | 5(5) | 2(2) | 6(6) | 5(5) |
可以看到,最终我们只需要输出d[1][1]就ok了,省去了很多的麻烦
那么递推代码如下(也能AC):
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int n, x;
int d[105][105] = { 0 };
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> d[i][j];
}
}
//正片开始
for (int i = n-1; i >= 1; i--) { //从倒数第二行开始
for (int j = 1; j <= i; j++) {
d[i][j] += max(d[i + 1][j], d[i + 1][j + 1]);
}
}
cout << d[1][1];
}
可以看到代码少了很多,而且复杂度为n^2
那在递归搜索一下,代码会更简单(但会运行超时,只有57分)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, x;
int d[105][105] = { 0 }, r[105][105] = {0};
int dfs(int i, int j) {
/*if (i == n)return d[i][j];
return d[i][j] += max(dfs(i + 1, j), dfs(i + 1, j + 1));*/
if (i == n)return d[i][j]; //递归到边界了,返回
return r[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + d[i][j];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> d[i][j];
}
}
//正片开始
//让d数组始终保持数字三角形的数据原状态,避免递归数据添加混乱
for (int i = 1; i <= n; i++)r[n][i] = d[n][i];//r数组是从底往上走,这里先初始化底部的数据
//但其实这个for的初始化赋值也可以省略掉,因为递归过程已经帮我们算进去了
cout << dfs(1,1);
}
dfs中注释的是我一开始写的递归,但发现数据好像被重复计算,导致数据加进去会有误,所以搞了一个辅助数组r
那为什么会超时呢,因为有大量的重复计算,此时,我们只需要小小的加一个记忆化的代码就ok了
也就是当r[i][j]>0的时候直接return 因为r[i][j]已经被max()中计算过了,不需要在回头算
代码如下(AC):
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, x;
int d[105][105] = { 0 }, r[105][105] = {0};
int dfs(int i, int j) {
if (r[i][j])return r[i][j];//记忆,默认为0,大于0说明已经算过了
if (i == n)return d[i][j]; //递归到边界了,返回
return r[i][j] = max(dfs(i + 1, j), dfs(i + 1, j + 1)) + d[i][j];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> d[i][j];
}
}
//正片开始
cout << dfs(1,1);
}
复杂度为n^2
标签:10,试题,int,max,dfs,long,递推,解法,105 From: https://blog.csdn.net/weixin_67024935/article/details/137050192