线性动态规划

Coookie · 2025-08-16 17:25:28 · 算法·理论

线性动态规划

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

序言

1. dp 解决什么问题？

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

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

2. dp 有什么优点

对于刚刚的问题，可以轻松想到相似于 dfs 的递归形式：
int dfs(int n) {
if (n == 1 || n == 2) return 1;
return dfs(n - 1) + dfs(n - 2);
}
分析出递归算法的时间复杂度为 O(2^n) ，明显无法解决问题。

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

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];
}

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 这一项不延续之前的序列，创建一个新序列。\ 这两种情况都考虑完成后，我们就可以轻松得出状态转移方程：
```
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 。所以得出求解顺序：
```
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) 的二分查找了。

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);
}

LCS

最长公共子序列（ 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 。\ 所以，可以得出状态转移方程：

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 的遍历方式必然是：

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 即可：

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

因为其中用不到遍历 j ，所以我们从 1 到 n 遍历 i 即可：

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 数组的便利顺序：

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]（我们拾取物品的获利），和不选的操作取最大值即可。

附上代码片段：

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} 。\ 完整代码：

#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 枚举拿了多少物品。可得代码：

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)

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

#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 背包思路，这样不一定可以获得最大值。不妨先遍历选择多少个，然后再计算价值：

#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 进行输入并处理，二进制拆分的代码大概长这样：

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)，所以完整代码长这样：

#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] 的工作状态 (原始)：\
$[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 的区间（初始值），然后先遍历区间长度（因为先计算小区间后合并大区间）、后枚举起点（之后一般会推出中点）：

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 练习题单。\ 如果文章出现说明不清楚或错误的地方，欢迎评论区指正。