Theme NexT works best with JavaScript enabled

人生若只如初见

📢📢📢:博主开学了!封闭中!

数塔问题-简单的动态规划

如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大。

1
2
3
4
5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

算法分析

我们可以这样想,从最后一层倒过来看,到倒数第二层,可以选择一个较大的路径,例如,假设我们一步走到了2这里,下一步应该怎么走?只有19或7这两种选择,既然我们想让总的路径之和最大,那我们肯定每一步都要选大的。我们人脑编译器是很简单的,每次只需要倒着推,到最后一个数据就是我们的最大路径。

数据结构

假设这个数塔的层数是N,我们可以将这个数塔放在一个NxN的data数组里,也许只需要下三角矩阵i>=j。另外,我们还就可以将每一步最大的路径的数据保存在dp数组里。用两重循环来遍历数组,我们要倒着推,所有要i–,二维的j是从左往右,j++。

data
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16
dp
59
50 49
38 34 29
21 28 19 21
19 7 10 4 16

代码

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
30
31
32
#include <iostream>
#define N 101
//最后一层的我们需要多加一层空白数据,不然会数组下标错误
using namespace std;

int max(int a, int b){
return a>b?a:b;
}

int data[N][N];//全局变量已初始化0
int dp[N][N];

int main() {
int n;
cout<<"请输入数塔的层数:(不超过100)"<<endl;
cin>>n;
cout<<"请输入塔的数据"<<endl;
for (int i = 0; i < n ; ++i) {
for (int j = 0; j <= i ; ++j) {
cin>>a[i][j];
}
}
for (int i = n-1; i >=0 ; --i) {
for (int j = 0; j <= i ; ++j) {
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+data[i][j];
//最后一层dp数据和data一样max(0,0)
}
}
cout<<"最大的路径和是:"<<dp[0][0];

return 0;
}

输出

1
最大路径和是:59

优化

输出路径

题目可能会要求我们输出我们是怎么走的,在两个表都填写完整后,第一步不用说,肯定的是data[0][0],之后,我们用dp[i][j](还是从dp[0][0]开始)数据减去data数组的这一个位置的数据,我们可以倒着想,我们是用下面两个数据的较大的一个加上data[i][j]数据得到这个dp[i][j]。相减的结果就是较大的那个dp[i+1][j]或者是dp[i+1][j+1]。我们就可以确定是选择了这个路径data[i+1][j]或data[i+1][j+1]。因为这一次我们是正着走的,一条路走到底,每次都选dp大的那一个data数据,只需要循环N-1次就可以了(第一步已确定)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print()
{
int node_value;
// 首先输出塔顶元素
cout << "最大路径:" << data[0][0];
int j = 0;
for (int i = 0; i < n-1; ++i)
{
node_value = dp[i][j] - data[i][j];
if (node_value == dp[i][j + 1]){
j++;//记录节点的列,输出要用
cout << "->" << data[i+1][j];
}//右边的大,应该往右走
else{
cout << "->" << data[i+1][j];
}//左边的大,应该往左走
}
cout << endl;
}

输出

1
最大路径:9->12->10->2->19

空间优化

其实dp数组里的数据不需要每一层都储存起来,用过之后就没用了,我们可以用覆盖的方法将二维数组优化为一维数组,也就是滚动数组。

参考博客:
动态规划:数塔问题——卡尔曼和玻尔兹曼谁曼

-------------------- ⭐本文结束⭐ --------------------