【算法笔记】动态规划基础（一）：dp思想、基础线性dp

前言

计算机归根结底只会做一件事：穷举。
所有的算法都是在让计算机【如何聪明地穷举】而已，动态规划也是如此。

---

动态规划的精髓

什么叫“状态”

每一个 DP 子问题，都可以用一组变量来唯一标识。把这组变量称为一个 “状态”，用 $dp[状态]$来表示该子问题的最优解（或方案数、合法性等）。

举个例子，我在实验室坐着敲代码，小王在图书馆站着处对象、小明在水房倒立洗头…

• 这里的（我，实验室，坐着，敲代码），（小王，图书馆，站着，处对象），（小明，水房，倒立，洗头）就是三组状态，可以用一个四维的数组来表示，$dp[i][j][k][l]$就表示$i$这个人，在$j$这个地方，以$k$这样的动作，干$l$这件事时的某种性质。

状态转移也好理解，举个例子：在游戏中，有几个技能，其中一个技能叫“转换”，可以让人物在跑、走、跳之间来回切换，消耗$a$点体力。其中一个状态转移就是消耗$a$点体力将走切换成跑，如果用$dp$数组表示放$i$次技能，达到当前状态消耗的体力的最小值，也就是$dp[i][跑]=min(dp[i][跑],dp[i-1][走]+a)$ ，这个式子就叫做状态转移方程。

动态规划的概念

前置知识：递归、递推

动态规划（Dynamic programming，简称DP） 是一种通过将原问题分解成几个彼此之间有关联的、相对简单的子问题来求解复杂问题的算法。

动态规划把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划的三要素

动态规划有很经典的三要素：重叠子问题、最优子结构、状态转移方程。

首先，虽然动态规划的核心思想就是穷举求最值或方案数，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的 「状态转移方程」 ，才能正确地穷举。而且，你需要判断算法问题是否具备 「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在 「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用 「记忆化」 来优化穷举过程，避免不必要的计算。

动态规划的框架

// 自顶向下递归的动态规划
int dp(状态1, 状态2, ...){for(int 选择 : 所有的选择){# 此时的状态已经因为做了选择而改变res = 求最值(res, dp(状态1, 状态2, ...));}return res;
}// 自底向上递推的动态规划
# 初始化 base case
dp[0][0][...] = base case;
# 进行状态转移
for(状态1 : 状态1的所有取值){for(状态2 : 状态2的所有取值){for(状态3 : 状态3的所有取值){dp[状态1][状态2][...] = 求最值(选择1, 选择2, ...);}}
}

无后效性

tips:动态规划的题要求你的转移无后效性，那什么叫无后效性呢

无后效性，即前面的选择不会影响后面的游戏规则。

寻路算法中，不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联，没有选择一说，所以也不存在后效性问题。

什么场景存在后效性呢？比如你的人生是否能通过动态规划求最优解？其实是不行的，因为你今天的选择可能影响未来人生轨迹，比如你选择了计算机这个专业，会直接影响到你大学四年学的课程、接触到的人，四年的大学生活因此就完全变了，所以根本无法与选择了土木工程的你进行比较。

有同学可能觉得这样局限是不是很大？其实不然，无后效性的问题仍然很多，比如背包放哪件物品、当前走哪条路线、用了哪些零钱，都不会影响整个背包大小、整张地图的地形、以及你最重要付款的金额…

dfs -> 记忆化搜索 -> dp

821. 跳台阶

暴力写法

#include <iostream>
#define endl '\n'
using namespace std;int f(int n){if(n == 0 || n == 1) return 1;return f(n - 1) + f(n - 2);
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;cout << f(n) << endl;return 0;
}

可以看出，暴力做法有很多递归的分支都是重复的，也就是有很多重复的子问题。这些重复的子问题在下一次遇到时如果每次都重新计算一遍就会很浪费时间，所以可以用一个数组记录一下，下次再遇到直接查表即可，这也就是记忆化搜索。

记忆化搜索写法

#include <iostream>
#define endl '\n'
using namespace std;int dp[16];int f(int n){if(dp[n]) return dp[n];if(n == 0 || n == 1) return 1;return dp[n] = f(n - 1) + f(n - 2);
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;cout << f(n) << endl;return 0;
}

记忆化搜索优化了什么？怎么转化成dp？

• 暴力：每个子问题都考虑一次。
• 记忆化搜索：对于相同的子问题，只考虑一次。

那是不是可以理解为：dp就是在暴力的基础上，把所有效果相同的状态都放在了一个集合里？暴力是单一状态和单一状态之间某种属性的转移，而dp是集合和集合之间某种属性的转移？

比如这道题，$dp[i]$表示的集合就是：所有从第$0$级台阶走到第$i$级台阶的合法方案。
属性就是：集合中元素的数量。

所以综上，$dp[i]$就表示：所有从第$0$级台阶走到第$i$级台阶的方案数。

dp写法

#include <iostream>
#define endl '\n'
using namespace std;int dp[16];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;dp[0] = 1, dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}cout << dp[n] << endl;return 0;
}

dp其实也是图论

首先先说结论：

动态规划 (DP) 很多时候其实就是在一个状态图（严格来说是一个有向无环图，DAG）上做一次「拓扑遍历＋松弛」的过程。

在动态规划（DP）中，我们把“子问题”看作图中的“节点”，把“从一个子问题推导到另一个子问题”的依赖关系看作有向边，那么所有这些状态和边就构成了一张有向无环图（DAG）。而对这张DAG做一次拓扑排序——恰好保证了：当我们要计算某个状态的最优值（或计数、最小／最大代价……）时，它依赖的所有前驱状态都已经计算完毕。

最大值、最小值，是不是相当于是求最长路、最短路，求方案数是不是就相当于是沿着拓扑序列累加？

状态DAG是怎样的？

• 节点（state）
  每一个 DP 子问题 $S$ 都对应 DAG 中的一个节点。
  例如，经典“爬楼梯”问题中，让 $dp[i]$ 表示到达第 $i$ 级台阶的方案数，
  那么节点就是 $0,1,2,\dots ,n$。

• 有向边（依赖）
  如果计算 $dp[v]$ 需要用到 $dp[u]$，就在 DAG 中加一条从 $u$ 指向 $v$ 的边。
  爬楼梯里，$dp[i]$ 可由 $dp[i-1]$ 和 $dp[i-2]$ 推出，就有两条边：
  $(i-1)\to i,(i-2)\to i$。

• 无环
  DP 的定义通常是“从小问题推向大问题”，不存在循环依赖，图上必然是无环的。

dp问题的初始化

dp问题的初始化经常不是很好理解，但如果你站在拓扑排序、最短路问题的角度来看，就会相对好理解一些。

回忆一下你学过的所有的最算路问题，代码是不是都有这样的两部分初始化：

memset(dist, 0x3f, sizeof dist); // 所有点dist初始化成正无穷
dist[s] = 0; // 源点dist初始化成0

dp问题的初始化其实也是这样的，分成两部分：

• 对所有的点进行初始化：比如求最小值，memset(dp, 0x3f, sizeof dp)。
  对于这种初始化，一般如果是求最小值，就初始化成一个极大值；如果求最大值，就初始化成一个极小值；如果是求数量，就初始化成0。
• 对“源点”进行初始化：单源最短路的问题源点只有一个，就给源点初始化成0，而拓扑排序就相当于是一个多源的最短路，源点就是所有入度为0的点，在dp中也就是那些最基本的状态（base case），这种初始化只需将所有的base case都按dp状态表示的含义，初始化成对应的数即可。比如数字三角形问题中：最顶端的点不能由任何点走过来，于是直接将其初始化成对应的值，或者你可以看做最顶端的点可以由上面下标为0的点走过来，所以也可以将所有下标为0的点初始化成0。

很多问题对“源点”的初始化经常会初始化下标为$0$的位置，像下面这样：

	for(int i = 1; i <= n; i++){dp[i][0] = i;}for(int i = 1; i <= m; i++){dp[0][i] = i;}

怎么确定base case呢？一般来说，如果你的dp遍历是for(int i = a; ...)，那base case就很有可能是你的i = a的前一个状态（前驱结点），多维也是同样的道理。

简单来讲，一个dp问题，你循环遍历的所有点都是状态DAG上入度不为0的点，你单拎出来初始化的点都是状态DAG入度为0的点。

dp问题的答案

和初始化相同，初始化是初始化所有的“起点”（入度为0的点），那答案就是所有的“终点”（出度为0的点），如果“终点”有很多个，就要定义一个结果变量，对于求最值，需要遍历一下所有出度为0的状态取个最值；对于求方案数，需要逐个判断、累加一下。

分析dp题的步骤

• 做dp题，首先就要把dp数组写出来，首先要想：dp数组要开几维：一般来说，如果不优化状态表示的话，有几个状态dp数组就要开几维。
• 然后，搞明白你dp数组的含义，也就是搞明白集合的表示和集合的属性。集合的属性常见的可能有最大值（max）、最小值（min）、数量（cnt）…
• 最后，写出状态转移方程，对应的过程就是将问题分成若干子问题的过程，也就是集合的划分。
• 然后，想怎么初始化，求最大值就初始化成极小值、求最小值就初始化成极大值、求数量就初始化成0…
• 然后，写代码：定义dp数组、初始化、for循环枚举所有的状态，输出结果。

具体各个过程都是什么意思：看下面的几个线性dp经典模型。

数字三角形

898. 数字三角形

状态表示

因为有行和列，所以状态要开二维:$dp[i][j]$

• 集合：所有从$a[1][1]$走到$a[i][j]$的路线
• 属性：（路线经过数字和的）最大值（max）

综上：$dp[i][j]$:所有从$a[1][1]$走到$a[i][j]$的路线的数字和的最大值

状态计算

集合划分：将这个集合划分成几个不同的集合，就要找一个不同的步骤。

可以看出，走到$a[i][j]$的这最后一步可以是从$a[i-1][j]$走过来的，也可以是从$a[i-1][j-1]$走过来的，所以可以从最后一步来划分这个集合，前一个集合是$dp[i-1][j]$，后一个集合是$dp[i-1][j-1]$。

显然：$dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j])$

初始化

要求最大值，并且有负数，先将所有位置都初始化成负无穷。

因为和要从0开始加，而不是负无穷，所以要将所有的$dp[0][j]$和$dp[i][0]$都初始化成0。

但上面这样比较麻烦，因为所有路线都是从起点开始走的，所以直接将起点初始化成$a[1][1]$，循环从$2$开始遍历即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 505;int a[N][N];
int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){cin >> a[i][j];}}memset(dp, -0x3f, sizeof dp);dp[1][1] = a[1][1];for(int i = 2; i <= n; i++){for(int j = 1; j <= i; j++){dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];}}int res = -0x3f3f3f3f;for(int i = 1; i <= n; i++) res = max(res, dp[n][i]);cout << res << endl;return 0;
}

最长上升子序列（LIS）

895. 最长上升子序列

状态表示

序列只有一维，dp数组也开一维就够了: $dp[i]$

• 集合：所有以$a[i]$结尾的上升子序列
• 属性：（长度的）最大值

综上：$dp[i]$：所有以$a[i]$结尾的上升子序列的长度的最大值。

状态计算

集合划分：将这个集合划分成几个不同的集合，就要找一个不同的步骤。

因为最后一步都是相同的，都是将$a[i]$加到序列中，无法划分，所以看倒数第二步：也就是加$a[i]$前这个上升子序列是以什么元素结尾的。想一下，如果$a[i]$能加到一个以$a[j]$结尾的上升子序列的后面，是不是一定要满足$a[i]>a[j]$ ?

所以这个集合就可以划分成：所有满足$a[i]>a[j]$( $0$ $\le$ $j$ $<$$i$)的以$a[j]$结尾的上升子序列接上一个$a[i]$。

状态转移方程就出来了：$dp[i]=max(dp[i],dp[j]+1)(a[j]<a[i])$。

初始化

求最大值，上升子序列最短都是1，都初始化成1即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int a[N];
int dp[N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];dp[i] = 1;}for(int i = 1; i <= n; i++){for(int j = 1; j < i; j++){if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);}}int res = 1; for(int i = 1; i <= n; i++) res = max(res, dp[i]);cout << res << endl;return 0;
}

优化

很显然，用dp求LIS是$O(n^2)$的，如果$n$比较大会超时，但可以基于贪心+二分、单调栈、单调队列等多种方式进行优化到$O(nlogn)$、$O(n)$，因为这是dp专题，就不细讲了。

最长公共子序列（LCS）

897. 最长公共子序列

状态表示

有两个序列，一个序列开一维，两个序列就开二维：$dp[i][j]$

• 集合：所有$a$的前$i$个元素和$b$的前$j$个元素的公共子序列
• 属性：（长度的）最大值

综上：$dp[i][j]$表示所有$a$的前$i$个元素和$b$的前$j$个元素的公共子序列的长度的最大值。

状态计算

集合划分：将这个集合划分成几个不同的集合，就要找一个不同的步骤。

看最后一步，$a$的前$i$个元素的子序列里，是不是有的带$a[i]$，有的不带$a[i]$? $b$的前$j$个元素的子序列里，是不是有的带$b[j]$，有的不带$b[j]$?那二者的公共子序列是不是也如此？

所以可以以$a[i]$和$b[j]$是否包含在公共子序列中为依据进行划分。

然后想这几个集合的状态怎么表示，可以分成下面四种情况：

• 情况1：$a[i]$,$b[j]$ 均存在于 最长公共子序列中 (前提$a[i]==b[j]$)
• 情况2：$a[i]$ 在，$b[j]$ 不在 （无前提）
• 情况3：$a[i]$, $b[j]$ 均不在 （无前提）
• 情况4：$a[i]$不在，$b[j]$在 （无前提）

初步想一下，是不是可以表示成下面这样：

• 情况1：暂用$dp[i-1][j-1]+1$表示
• 情况2：暂用$dp[i][j-1]$表示
• 情况3：暂用$dp[i-1][j-1]$表示
• 情况4：暂用$dp[i-1][j]$表示

但这样表示真的对吗？事实上是不严谨的，举个例子：$dp[i][j-1]$的集合表示的是所有$a$的前$i$个元素和$b$的前$j-1$个元素的公共子序列，$b$的前$j$个元素一定是不包含$b[j]$的，但 $a$的前$i$个元素是不是可能包含$a[i]$，也可能不包含$a[i]$? $dp[i-1][j]$也是一样的道理

所以实际上 $dp[i-1][j]$表示的是情况2+情况3，$dp[i][j-1]$表示的是情况3+情况4 。

因为这个模型dp的属性是求最大值，集合之间有交集不会影响答案，保证不漏就行(就好像你要求10个数的最大值，你知道前7个数的最大值和后7个数的最大值，只需要这两个集合取max就可以了），所以状态计算直接取$dp[i-1][j-1]+1$、$dp[i][j-1]$、$dp[i-1][j]$三者的最大值就可以了。

状态转移方程也就出来了：
$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
$dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)(a[i]==b[j])$

也可以换种方式理解：对于字符串$a$和$b$中的每个字符都有且只有两种状态：在公共子序列中和不在公共子序列中。那是不是可以从后往前遍历每一个字符：如果$a[i]==b[j]$，这个字符就一定在公共子序列中，也就是情况1，而如果$a[i]\ne a[j]$，这两个字符就至少有一个不在公共子序列中，需要丢弃一个，也就是情况2、3、4。

初始化

求最大值，公共子序列最小都是0，都初始化成0即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;cin >> n >> m;string a, b;cin >> a >> b;a = " " + a, b = " " + b;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= m; i++) cin >> b[i];for(int i = 1; i <= n; i++){for(int j = 1; j <= m; 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);}}cout << dp[n][m] << endl;return 0;
}

最短编辑距离

902. 最短编辑距离

状态表示

有两个字符串，开两维，$dp[i][j]$

• 集合：所有让$a$的前$i$个字符和$b$的前$j$个字符变得相同的操作方式
• 属性：（操作次数的）最小值

综上：$dp[i][j]$表示所有让$a$的前$i$个字符和$b$的前$j$个字符变得相同的操作次数的最小值。

状态计算

集合划分：将这个集合划分成几个不同的集合，就要找一个不同的步骤。

还是看最后一步，最后一步肯定是改变$a$的一个字符后 $a[1$ ~ $i]$ 变得和$b[1$ ~ $j]$相同，而改变字符有三种方式：增加、删除和替换。

首先要弄清楚一点，插入操作实际上是在末尾添加一个字符，删除操作一定是删掉最后一个字符。

为什么呢？拿删除举例子，首先，如果你某一步的操作是删除中间的字符，删除位置后面的整个序列都会改变，这就不满足无后效性。其次，如果某一步删除操作删除的是中间的字符，那么这个操作在之前一定可以通过删除最后的字符来实现，也就相当于是之前漏删了，后面来补，并且末尾的$b[j]$也没动到，这一定不是最优的子结构，并且如果你某一步的操作是删除中间的字符，每次删除的位置都难以决定，这也就不是重叠的子问题。

而如果你每次都删最后的字符，每次操作都是相同的，也不会影响后面的决策，并且是最优的。

任何最优路径的最后一步，绝不会故意留一段未对上的后缀不管，再去中间做事然后回来补尾巴。

• 如果最后一步是增加一个字符：为了让$a[1$ ~ $i]$ 变得和$b[1$ ~ $j]$相同，最后加的字符就一定是$b[j]$，而$a[1$ ~ $i]+b[j]$和$b[1$ ~ $j]$相同，也就说明$a[1$ ~ $i]+b[j]$和$b[1$ ~ $j-1]+b[j]$相同，也就说明原来的$a[1$ ~ $i]$ 和$b[1$ ~ $j-1]$是相同的，也就是$dp[i][j-1]+1$

• 如果最后一步是删除某个字符：删掉的字符一定是$a[i]$，而如果删$a[i]$后$a[1$ ~ $i]$ 变得和$b[1$ ~ $j]$相同，就说明$a[1$ ~ $i]-a[i]$ 和$b[1$ ~ $j]$相同，也就是$a[1$ ~ $i-1]+a[i]-a[i]$ 和$b[1$ ~ $j]$相同，也就是$dp[i-1][j]+1$

• 如果最后一步是改变某个字符：
  如果$a[i]\ne b[j]$，就一定要把$a[i]$改成$b[j]$，如果改之后相同了，就说明$a[1$ ~ $i-1]+b[j]$ 和$b[1$ ~ $j]$相同，也就是$a[1$ ~ $i-1]+b[j]$ 和$b[1$ ~ $j-1]+b[j]$相同，也就是$a[1$ ~ $i-1]$ 和$b[1$ ~ $j-1]$相同，也就是$dp[i-1][j-1]+1$

  如果$a[i]=b[j]$，最后的字符就不用管，只需将$a[1$ ~ $i-1]$ 和$b[1$ ~ $j-1]$变得相同，也就是$dp[i-1][j-1]$。

然后可以得出状态转移方程：
$dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)$
$dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(a[i]\ne b[j]))$

初始化

求最小值，最大的编辑距离也就是全改一遍的情况，状态转移的起点也就是空串的时候，这时候恰巧是全改，只需给所有的$dp[i][0]、dp[0][i]$都初始化成$i$即可。

AC代码

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int N = 1010;int dp[N][N];int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int n, m;string a, b;cin >> n >> a >> m >> b;a = " " + a;b = " " + b;for(int i = 1; i <= n; i++){dp[i][0] = i;}for(int i = 1; i <= m; i++){dp[0][i] = i;}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1; // 增和删if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]); // 不用改else dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1); // 改}}cout << dp[n][m] << endl;return 0;
}