#创作计划# 动态规划《数字金字塔》教程

深搜邈和广搜邈

2025-01-14 13:54:37

发布于：上海

7阅读

0回复

0点赞

前言

动态规划 $(Dynamic\,Programming)$ ，简称 $DP$ 。仔细想一下，动态规划这个东西不走回头路，有点像贪心和递推的结合体，因此可以成为 $CSP-J$ 的考纲范围内的算法知识点。如何学好动态规划？首先就要吃透一道很基本的题目：数字金字塔。

正文

要能够学好动态规划，尤其是到了后面背包等问题，首先要知道状态转移方程式的由来。本文介绍四种数字金字塔的解题思路和方法，望对大家动归的学习路上有帮助。

首先，要了解一点：一道题目会有不同的思路和思考方向，这些不同的思路和方向就会带来不同的解题过程和代码。数字金字塔是个很好的例子，它可以从上往下顺着题目要求推出结果，也可以从下往上逆着它的要求来得到正解。
我们先考虑顺推，如法一和法二所示。

方法一：顺推法

在开始之前，先确定一点：设 $dp$ 数组，其中 $dp[i][j]$ 表示从顶端走到节点 $(i,j)$ 得到的最大的和，并且强制以节点 $(i,j)$ 作为终点。
根据题意，节点 $(i,j)$ 可以从 $(i-1,j-1)$ 和 $(i-1,j)$ 走过来。用到贪心的思想，为了得到最大值，我们必须取 $\max(dp[i-1][j-1],dp[i-1][j])$ ，再加上走到了节点 $(i,j)$ 时新获得的数据 $a[i][j]$ ，可以得出转移方程式：

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

如果把 $a[i][j]$ 忽略，改成变量 $k$ ，则应当在双重循环中读入 $k$ ，然后推出 $dp[i][j]$ ，既节省了空间又节省了读入 $a[1001][1001]$ 二维数组的时间。
因此，可以写出下列代码：

#include<iostream>
using namespace std;
#define int long long
int dp[1001][1001],k,n,ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>k;
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+k;
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

不过，如果所谓的行数 $n$ 过于大，那么毋庸置疑的是，开二维数组必然会爆空间，你就喜提一个 $\blue{MLE}$ 了。这时候，就要用一维数组上场替换二维数组。

方法二：一维顺推

如果所谓的行数 $n$ 过大超过大约 $3000$ 的话，由于状态转移方程式中只涉及到 $dp[i-1][j]$ 和 $dp[i-1][j-1]$ 两者，可以考虑只开一维数组（当然也可以开滚动数组），代替二维。
状态转移方程式变为了：

$dp[j]=\max(dp[j-1],dp[j])+k$

唯一的麻烦就是如果从左往右存储会发生当 $m=j+1$ 时， $dp[j]$ 发生改变后 $dp[m]=max(dp[m-1],dp[m])+k$ 这里 $dp[m-1]$ 已经是更新过后的值了，不符合题意。因此，必须从右往左存储。

#include<iostream>
using namespace std;
#define int long long
int dp[100001],k,n,ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=i;j;j--){
			cin>>k;
			dp[j]=max(dp[j],dp[j-1])+k;
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}

这种用一维数组来代替二维数组的方法在背包问题的学习中也很常见，01背包开二维数组开不下时可以考虑开一维数组代替，其原因和上述原因大同小异。而且开了一维数组后完全背包问题会得到简化。如果加上多重背包，那么混合背包使用一维数组确实会更方便。

每种方法都有它的优点和缺点，而两种不同的方法根据它们优缺点不同，可能会适用于不同场景。说完了顺推，我们再来聊聊逆推，的确逆推有时候会比顺推更有用。

方法三：逆推法

顺推法有优点也有缺点。优点是方法简单容易想到，而且可以优化空间省去数组 $a[1001][1001]$ 。
但是缺点是它有多个终点，直接输出 $dp[n][n]$ 明显不是最大值，必须遍历一遍最后一行获得最大值输出。
因此，我们可以考虑设置多个起点出发回到同一个终点。这就是逆推法主要思想。这种思想可能更适用于倒着给出的数字金字塔。
状态转移方程式只不过是把顺推的过程逆过来，还是求最大，因此 $\max$ 函数不变，加上的东西也不变。经过改变，状态转移方程式如下：

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

当然，这里需要先输入所有的 $a[i][j]$ ，再进行逆推过程，不能省去 $a[1001][1001]$ 这个二维数组。

#include<iostream>
using namespace std;
#define int long long
int dp[1001][1001],a[1001][1001],n;
signed main(){
	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;i--)dp[n][i]=a[n][i];
	for(int i=n-1;i;i--){
		for(int j=1;j<=i;j++){
			dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]);
		}
	}
	cout<<dp[1][1];
	return 0;
}

方法四：一维逆推

和顺推法一样，逆推法的 $dp[1001][1001]$ 是二维数组，当所谓的行数 $n$ 超过大约 $3000$ 时，空间就会不够。因此，如果题目给的是倒着的数字金字塔，我们考虑逆推法的一维状态转移方程式。
由逆推法知道， $dp[i][j]=\max(dp[i+1][j],dp[i+1][j+1])+a[i][j]$ ， $dp[i][j]$ 只取决于 $dp[i+1][j]$ 和 $dp[i+1][j+1]$ ，因此降维操作不影响结果，则状态转移方程式变为：

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

令 $m=j+1$ ，则先推完 $dp[j]$ ，取决于 $dp[j]$ 和 $dp[m]$ ，而 $dp[m]$ 这一轮还没有推；再推 $dp[m]$ ，涉及到 $dp[m]$ 和 $dp[m+1]$ ，没涉及到 $dp[j]$ 。因此，逆推法用一维数组实现，循环不用从后往前，直接从前往后推即可。
不过，对于正着的数字金字塔，逆推用一维数组和用二维数组没什么大的区别，因为你的 $a[1001][1001]$ 没办法得到简化。

#include<iostream>
using namespace std;
#define int long long
int dp[1001],a[1001][1001],n;
signed main(){
	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;i--){
		for(int j=1;j<=i;j++){
			dp[j]=a[i][j]+max(dp[j],dp[j+1]);
		}
	}
	cout<<dp[1];
	return 0;
}

后记

每种方法都有各自的优点和缺点。具体情况还需根据题目要求来判断用什么方法。
唯一不变的是吃透数字金字塔很有必要。在后续的LIS和LCS等问题中，状态转移方程式逐渐从具体的意想到的这种变得抽象，必须像这道题一样一眼识破 $dp$ 数组每一个位置代表的含义，并推断出状态转移方程式；在以后的背包问题中，一题多解的情况很常见，可以用二维数组，可以优化为一维数组，还可以通过二进制优化成普遍的背包问题。因此，学好了数字金字塔对于以后的问题都很有帮助。

有帮助，赞一个

去预览

0/2000

这里空空如也

前言

正文

方法一：顺推法

方法二：一维顺推

方法三：逆推法

方法四：一维逆推

后记

热门讨论