线性动态规划

动态规划（即Dynamic programming，简称DP）是一种常用的算法，采用递推思路，其时间复杂度较低、空间复杂度较高。

序言

1. dp解决什么问题？

dp可以高效解决具有重叠子问题和最优子结构的问题，比如：

请求出斐波那契数列的前1e7项。

2. dp有什么优点

对于刚刚的问题，可以轻松想到相似于dfs的递归形式：

CPP

int dfs(int n) {
    if (n == 1 || n == 2) return 1;
    return dfs(n - 1) + dfs(n - 2);
}

分析出递归算法的时间复杂度为

O(2^n)

，明显无法解决问题。

那么，不妨尝试一种思想，尝试记忆化搜索和递推。

CPP

const int N = 1e7 + 5;
int a[N];

int dfs(int n) {
    if (n == 1 || n == 2) return 1;
    if (!a[n]) return a[n];
    a[n] = dfs(n - 1) + dfs(n - 2);
    return a[n];
}

CPP

int dp() { // 仅用于演示，实际代码直接放入主函数即可
    dp[1] = dp[2] = 1;
    for (int i = 3;i <= n;i++)
        dp[i] = dp[i - 1] + dp[i - 2];
}

这两种方法的时间复杂度是

O(n)

，时间复杂度上绰绰有余，但空间复杂度从

O(1)

升到了

O(n)

。不难感受到dp的优点——空间换时间。
实际上，记忆化搜索可以说是一种dp，算是dp的前身。

3. 如何使用dp解题

让我们通过刚刚的dp代码继续分析如何使用dp解题。
分析一个dp问题一共有5步：

	步骤	举例
1	明确dp数组含义	斐波那契第 $i$ 项的值
2	推导状态转移方程	$dp_i = dp_{i - 1} + dp_{i - 2}$
3	dp数组初始值	$dp_1 = dp_2 = 1$
4	求解顺序	$for(i: 3\sim n)$
5	最终答案	$dp_n$

4. dp解题规律

刚刚已经提到dp算法分5步解决，但是不是每一个问题都想斐波那契那么简单，实际上，dp算法的设计有一定的规律和技巧。

	步骤	规律
1	明确dp数组含义	题目问什么dp就是什么意思
2	推导状态转移方程	根据dp数组推
3	dp数组初始值	正常状态转移方程考虑不到的特殊值
4	求解顺序	状态转移时需要上一步求出什么
5	最终答案	根据dp数组推

特别注意：dp数组的维度由需要几个参数决定，类似于dfs中加参数剪枝，其中可以思考如果参数可以被另一个参数通过某种方式推出来，就可以时间换空间减少维度，在某些题中发挥了重要作用。

序列dp

序列dp，顾名思义，即在序列（数组、字符串等）上做dp，典型题目有最长上升子序列、最长公共子序列等。

判定特点

给定数组/字符串求最长/最大/最短/最小的某值。
dp数组状态定义： $dp_i:$ 以 $a_i$ 结尾时的状态。

LIS

最长上升子序列（Longest Increasing Subsequence，LIS），顾名思义，就是求出在一个数列的上升子序列中最长的那个。
让我们举个例子：在数列1 2 3 2 4 5 6 7中，上升子序列有很多，如1 2 3，2 4等，而其中最长的一个，就是1 2 4 5 6 7，即最长上升子序列。强调：字符串中的子串要求连续，子序列可以断开。

朴素 $O(n^2)$

理解题意后，我们就可以开始思考dp的5步：

dp含义：题目问的是最长上升子序列长度，需要知道的变量条件为 $n$ ，所以需要一个dp参数， $dp_i$ 的含义是数组前 $i$ 个数的最长上升子序列长度。
推导状态转移方程： 考虑 $dp_{i - 1}$ 对 $dp_i$ 的影响。我们可以分成两种情况讨论：
一、 $dp_i$ 加入 $dp_{i - 1}$ 所计算出的最长上升子序列，前提是满足上升的要求；
二、 $dp_i$ 这一项不延续之前的序列，创建一个新序列。
这两种情况都考虑完成后，我们就可以轻松得出状态转移方程：

CPP

dp[i] = 1; // 默认创建一条LIS
// 中间要加入有关j的循环，后续会提到
if (a[j] < a[i]) dp[i] = max(dp[i],dp[j] + 1); // 如果可以添加在上一串LIS后面

dp数组初始值：因为前0项的LIS长度为0，所以 $dp_0 = 0$ ，如果dp数组定义在main()函数外面默认初始值为0，那么初始值定义可以忽略。
求解顺序：首先，dp函数需要枚举 $dp_i$ ；其次，因为需要进行加入LIS尾部验证，我们要枚举在 $i$ 之前的 $j$ 。所以得出求解顺序：

CPP

for (int i = 1;i <= n;i++) {
   // ...
   for (int j = 0;j < i;j++)
       // ...
}

最终答案：根据dp数组的含义与需求答案，可以知道输出 $dp_n$ 即可。

于是，LIS问题的求解就完成了。

拓展 $O(nlogn)$

虽然刚刚的dp做法已经足够解决大部分问题，但时间复杂度仍然会达到

O(n^2)

。不妨再结合一些贪心思想考虑。
当上升子序列长度固定，那么最后一个数越小，后续接上这段上升子序列显然就会更简单一点。
因此，我们可以尝试：

dp_i

即为长度为

i

的最长上升子序列中最小的结尾，每次分析一个新的

a_i

就寻找dp数组中第一个大于等于

a_i

的值，将其修改为

a_i

。
这还不够。此时的时间复杂度还是

O(n^2)

。那为何要把dp的含义设置成这样呢？请注意，此时因为dp记录的是上升子序列的最后一项，所以我们其实定义了一个有序的dp数组——有序就可以用 $O(logn)$ 的二分查找了。

CPP

int tmp = 0;
for (int i = 1;i <= n;i++) {
    int pos = lower_bound(dp + 1,dp + tmp + 1,a[i]) - dp; // 二分查找
    dp[pos] = a[i];
    tmp = max(tmp,pos);
}

最长公共子序列（Longest Common Subsequence，LCS）是指在两个序列之间中最长的公共子序列。这类问题与LIS相似，都是求一种长度。
举个例子，数列1 2 3 6 7 4和数列1 2 6 8 7 5 3的最长公共子序列就是1 2 6 7。
接下来开始构思dp算法。LIS算法中，因为只需要知道算到一个数组中的第几位，所以dp数组开一维。LCS中有两个数组，那么就应该开二维。所以，

dp_{i,j}

的含义就是数组a的前i项和数组b的前j项的LCS长度。
dp数组的含义明确后，我们就可以推出状态转移方程。思路是这样的：

dp_{i,j}

要么在

dp_{i - 1,j - 1}

的基础上延续最长公共子序列(即为

+1

)，要么就在之前最长公共子序列的基础上不改动——延续

dp_{i - 1,j}

和

dp_{i,j - 1}

中的较长的那一项。其中，延长最长公共子序列的前提是

a_i = b_j

。
所以，可以得出状态转移方程：

CPP

dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]); // 不改动
  if (A[i] == B[j]) dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1); // 满足条件就可以延续

那么，遍历顺序又是什么呢？我们知道，LCS也需要遍历

i

和

j

，根据dp数组的定义，

i

应该遍历

a

数组中的每一项，j应该遍历

b

数组中的每一项。既然

a

数组的长度为

n

，

b

数组的长度为

m

，那么

i

和

j

的遍历方式必然是：

CPP

for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++)

可以得出最开始遍历不到的位置就是

dp_{0,0}

，所以我们需要设置

dp_{0,0}

的初始值。因为两个空数组的LCS长度必定是0，所以dp[0][0] = 0，可以忽略。
最后，答案根据dp数组的含义，必定是

dp_{n,m}

。
这就是LCS的标准解法。

最大子段和

最大子段和可以说是很基础的序列dp问题，模板问题是这样的：

给出数组 $a$ 的元素 $a_1,a_2,...,a_n$ ，请取出中间连续且非空的一段，求这段的和的最大值。

大家可以先进行思考、写代码，我们直接考虑五步。
看完LIS和LCS可知，dp数组的含义就是需求答案，即

dp_i

代表数组前

i

项的最大子段和。
同样的，对于状态转移方程考虑选和不选，因为没有限制条件，所以直接取max即可：

CPP

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

因为其中用不到遍历

j

，所以我们从

1

到

n

遍历

i

即可：

CPP

for (int i = 1;i <= n;i++)

最后，因为最大子段和可以有很多段，我们需要在每一段中找最大的一段，所以，需要用

ans

在刚刚的

i

循环中存储

dp_i

的最大值。

背包dp

01背包

背包dp是dp中非常经典的题型。其中，01背包是最简单、基础的背包问题——其余背包问题基本上都是基于01背包的思路进行拓展。01背包的问题是这样的：

一件承重量为 $m$ 的背包想要装下 $n$ 个物品中的其中一部分，每个物品的重量为 $w_i$ ，价值为 $v_i$ ，求这个背包最多能装下多少价值的物品？

可能你已经想到了，为我们可以通过“选或不选”的思路分类讨论。但是，01背包的难点不是选或不选，而是dp数组的含义和遍历顺序。
dp数组一定代表了需要求的答案——价值。第一维度很容易想到，就是选择前

i

个物品的时候要求的答案。可是这一个维度远远不够——如何知道还有多少可用空间？所以，我们需要增加第二个维度，代表现在要求物品总重不超过

j

。
接下来，根据dp数组的含义，不难想到dp数组的便利顺序：

CPP

for (int i = 1;i <= n;i++) // 枚举物品
    for (int j = 0;j <= m;j++) // 枚举重量上限

这里的易错点是很多人习惯j从1开始枚举，但是实际上，重量上限可以为零。因此，j要从0开始枚举。

接下来就应该开始分析状态转移方程了。既然知道分类为“选或不选”，那么：

不选：
如果我们不想选，那么j不变，i继承i - 1的dp数据;
选：
选择的前提是剩下的j容量可以获取这个物品，因此需要加判断。然后，让 $dp_{i,j}$ 继承 $dp_{i - 1,j - w[i]}$ （减去重量得出上一个操作的结果）并加上 $v[i]$ （我们拾取物品的获利），和不选的操作取最大值即可。

附上代码片段：

CPP

dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i]);

最后，根据dp数组含义，答案即为

dp_{m,n}

。
完整代码：

CPP

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int w[N],v[N],dp[N][N];

int main() {
	int n,m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) cin >> w[i] >> v[i];
	for (int i = 1;i <= n;i++)
		for (int j = 0;j <= m;j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i]);
		}
	cout << dp[n][m] << endl;
    return 0;
}

完全背包

完全背包在01背包的基础上增加了一定难度：

一件承重量为 $m$ 的背包想要装下 $n$ 个物品中的其中一部分种类，每个种类物品可以重复选择，每个物品的重量为 $w_i$ ，价值为 $v_i$ ，求这个背包最多能装下多少价值的物品？

完全背包增加的难度就在于不限制选择数量。那么，让我们在01背包的基础上进行改进：增加循环变量k枚举拿了多少物品。可得代码：

CPP

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            for (int k = 1; k * w[i] <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }

思路很清晰，问题很明显：时间复杂度极高，不支持大数据。那么，我们就要想办法将其循环层数压到最多2层。
经过一系列证明(证明过程中的部分思路由AI生成，作者参考思路手动整理)：

数学证明

原始状态转移方程
对于完全背包问题，朴素解法的状态转移方程为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2v] + 2w, dp[i-1][j-3v] + 3w, ...)

优化推导

观察当 $j >= v$ 时的情况： dp[i][j] = max(dp[i-1][j], dp[i-1][j-v] + w, dp[i-1][j-2v] + 2w, ...)
而考虑 $dp_{i,j - v}$ 的表达式： dp[i][j-v] = max(dp[i-1][j-v], dp[i-1][j-2v] + w, dp[i-1][j-3v] + 2w, ...)
将 $dp_{i,j - v} + w$ 展开： dp[i][j-v] + w = max(dp[i-1][j-v] + w, dp[i-1][j-2v] + 2w, dp[i-1][j-3v] + 3w, ...)
对比发现：dp[i][j] = max(dp[i-1][j], dp[i][j-v] + w)

我们就可以轻松得出完全背包的模板程序了：

CPP

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int w[N],v[N],dp[N][N];

int main() {
	int m,n;
	cin >> m >> n;
	for (int i = 1;i <= n;i++) cin >> w[i] >> v[i];
	dp[0][0] = 0;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= m;j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) dp[i][j] = max(dp[i][j],dp[i][j - w[i]] + v[i]); 
		}
	cout << dp[n][m] << endl;
	return 0;
}

多重背包

多重背包的大致题意介于01背包和完全背包之间，但是却是相较有难度的题型：

一件承重量为 $m$ 的背包想要装下 $n$ 个物品中的其中一部分种类，每个种类物品可以选择 $a_i$ 个，每个物品的重量为 $w_i$ ，价值为 $v_i$ ，求这个背包最多能装下多少价值的物品？

用完全背包的思路会发现，如果可以选无数个就忽略了个数限制；用01背包思路，这样不一定可以获得最大值。不妨先遍历选择多少个，然后再计算价值：

CPP

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int v[N],w[N],m[N],dp[N][N];

int main(){
	int n,W;
	cin >> n >> W;
	for (int i = 1;i <= n;i++) cin >> v[i] >> w[i] >> m[i];
	for (int i = 1;i <= n;i++)
		for (int j = 0;j <= W;j++)
			for (int t = 0;t <= m[i];t++)
				if (j >= t * w[i])
					dp[i][j] = max(dp[i][j],dp[i - 1][j - t * w[i]] + t * v[i]);
	cout << dp[n][W] << endl;
	return 0;
}

可是，在这种三重循环的条件下，时间复杂度依然很高，dp算法难显优势。所以，这里我们要介绍的是各位以后也很可能遇到的知识点——二进制拆分。
其思路来源于每个十进制数和一个二进制表示一一对应，那么假如我们把这个十进制的取用数量

a

拆成一个二进制数，然后将每一位看做一个01背包的项目，就可以将多重背包转化为01背包。
那么，01背包部分想必通过之前的学习足以掌握，接下来的难点就是二进制化了。二进制的主要思路是每次取

z

的最后一位二进制(假设这是第

i

次进行此步骤)，通过计算权值(即

2^{i - 1}

)获得选择当前位的代价和收益，成为标准01背包模板题。
所以，我们可以使用三个临时变量

x,y,z

进行输入并处理，二进制拆分的代码大概长这样：

CPP

for (int i = 1;i <= n;i++)
{
	int x,y,z;
	cin >> x >> y >> z;
	int tmp = 1;
	while (z >= tmp)
	{
		v[++cur] = tmp * x;
		w[cur] = tmp * y;
		z -= tmp;
		tmp *= 2;
	}
	if (z > 0)
	{
		v[++cur] = z * x;
		w[cur] = z * y;
	}
}

后续进行01背包处理即可，注意我们进行二进制拆分，

int

范围以内数据位数不超过20，为了拆分必须算出

cur

范围(20 * 1e5)，所以完整代码长这样：

CPP

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int v[20 * N],w[20 * N],dp[N][N];

int main(){
	int n,W;
	cin >> n >> W;
	int cur = 0;
	for (int i = 1;i <= n;i++)
	{
		int x,y,z;
		cin >> x >> y >> z;
		int tmp = 1;
		while (z >= tmp)
		{
			v[++cur] = tmp * x;
			w[cur] = tmp * y;
			z -= tmp;
			tmp *= 2;
		}
		if (z > 0)
		{
			v[++cur] = z * x;
			w[cur] = z * y;
		}
	}
	for (int i = 1;i <= cur;i++)
		for (int j = 0;j <= W;j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= w[i]) dp[i][j] = max(dp[i][j],dp[i - 1][j - w[i]] + v[i]);
		}
	cout << dp[cur][W] << endl;
	return 0;
}

空间优化

dp算法相当于“空间换时间”，空间的消耗是非常大的。在此提供两种空间优化的思路，降低算法空间需求。
这两种优化比较相似，能够进行优化的条件是在状态转移过程中，当前状态仅依赖于前面几层的状态即可推出。

滚动数组

滚动数组是一种常见、简单的优化方法，形象地通过滚动的原理不断覆盖原数组、只保留有用内容不断迭代。
让我们用文字图例更深刻地理解一下：

滚动数组 $dp[2][N]$ 的工作状态(原始)：
$[1,2,3,4,5,6,7];$
$[a,b,c,d,e,f,g];$
加入一组数据(这组数据需要前一行-第一行推出)： $[1,2,3,4,5,6,7];$
$[8,9,10,11,12,13,14];$
加入一组数据(这组数据需要前一行-第二行推出)： $[h,i,j,k,l,m,n];$
$[8,9,10,11,12,13,14];$
以此类推。每一个递推周期有多长（即每行数据需要最多 $n$ 行以前的数据支撑推出），滚动数组的第一维度就开多大。

实际的实现也很方便。以背包dp常用的滚动数组优化为例，易知每一个物品的选择状态的计算只需要知道前一个物品的状态即可。所以，开dp[2][N]的数组完全足够。计算时只需要通过&简便运算就可以区分奇偶将数据分配进正确的滚动数组位置，如dp[i & 1][j]。这种优化操作简单，方便增加。

一维优化

一维优化把空间利用到了极致，但比较难写易出错。使用一维优化还要求推出dp数组仅依赖于上一层下标在一定范围内的 $j$ 状态。

一般情况下倒序更新

以01背包为例，

dp_{i,j}

的计算依赖于

dp_{i - 1,j}

和

dp_{i - 1,j - w_i}

，可以理解为上方和左上方。依赖于数据的左侧，我们必须从最右侧数据开始覆盖，保证有用数据在使用时不被覆盖。
实操的代码也很简单，只需要把数组设成1维dp[j]，第二层遍历

j

时倒序遍历即可。

完全背包正序更新

在完全背包中，计算

dp_{i,j}

的前提是

dp_{i - 1,j}

和

dp_{i,j - w_i}

，即上方和同行左侧。所以，我们不再需要知道上一行的左侧，但要先计算出同行的左侧，需要

j

顺序遍历。

总而言之，这两种优化都是在保留所需数据的前提下，不让无用数据浪费空间，空间活用的方法很好地提高了数组空间利用率。

棋盘dp(二维dp)

棋盘dp，即在二维条件上做的dp，思考方法和序列dp一样，只是需求条件可能出现在其他层。一般可以解决迷宫内路径数量等题目。这种题型没有模板，需要具体题目具体分析。

区间dp

区间dp的核心思想是小区间上dp得到的结果在大区间dp时要用，即小区间dp结果合并为大区间dp结果。
一般的区间dp都需要枚举出所有可能区间进行合并，dp[i][j]数组的含义往往是区间[i,j]中所求的最优解。
一般的区间dp有统一的遍历模板，最开始处理长度为1的区间（初始值），然后先遍历区间长度（因为先计算小区间后合并大区间）、后枚举起点（之后一般会推出中点）：

CPP

for (int i = 1;i <= n;i++) dp[i][i] = a[i]; // 处理dp初始值的一个例子
for (int len = 2;len <= n;len++)
		for (int i = 1;i + len - 1 <= n;i++)
			int j = i + len - 1; //可以通过i和len推出终点

结语

到这里，线性dp的大部分主要内容就讲解完成了。做dp练习题的时候，请一定记住dp五大因素步骤，尝试通过原理推出代码。可以尝试推荐的洛谷线性dp练习题单。
如果文章出现说明不清楚或错误的地方，欢迎评论区指正。

线性动态规划

文章操作

线性动态规划

序言

1. dp解决什么问题？

2. dp有什么优点

3. 如何使用dp解题

4. dp解题规律

序列dp

判定特点

LIS

朴素 $O(n^2)$

拓展 $O(nlogn)$

LCS

最大子段和

背包dp

01背包

完全背包

数学证明

优化推导

多重背包

空间优化

滚动数组

一维优化

一般情况下倒序更新

完全背包正序更新

棋盘dp(二维dp)

区间dp

结语

相关推荐

评论

线性动态规划

文章操作

线性动态规划

序言

1. dp解决什么问题？

2. dp有什么优点

3. 如何使用dp解题

4. dp解题规律

序列dp

判定特点

LIS

朴素 O(n2)O(n^2)O(n2)

拓展 O(nlogn)O(nlogn)O(nlogn)

LCS

最大子段和

背包dp

01背包

完全背包

数学证明

优化推导

多重背包

空间优化

滚动数组

一维优化

一般情况下倒序更新

完全背包正序更新

棋盘dp(二维dp)

区间dp

结语

相关推荐

评论

朴素 $O(n^2)$

拓展 $O(nlogn)$