4 - 线性DP
非常哈人动态规划，使我脑子旋转。
概念
DP求值/递推的顺序是线性的，例如背包问题。
例题
数字三角形
898. 数字三角形 - AcWing题库
数字三角形可用一个二维数组存储：
1 2 3 4 5
---------------
1 | 7
2 | 3 8
3 | 8 1 0
4 | 2 7 4 4
5 | 4 5 2 6 5首先分析 状态表示：这是一个二维的状态f(i, j)，它表示所有从起点(1, 1)走到当前位置(i, j)路径和的最大值。
然后分析 状态计算：对集合f(i, j)进行划分，可以发现可由f(i - 1, j - 1)或f(i - 1, j)到达f(i, j)。那么状态转移方程为f(i, j) = max(f(i - 1, j - 1), f(i - 1, j)) + a[i][j]，其中a是存储数字三角形节点值的二维数组。
参考代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n + 5, vector<int>(n + 5, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
cin >> a[i][j];
// dp, 题中三角形节点值可能是负数, 所以初始化为-INF
vector<vector<int>> dp(n + 5, vector<int>(n + 5, -INF));
// f(1, 1)只有一种可能, 得初始化
dp[1][1] = a[1][1];
// 然后从第二行开始dp
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
// 最后需要遍历最后一行取最大值
int ans = -INF;
for (int i = 1; i <= n; ++i)
ans = max(ans, dp[n][i]);
cout << ans;
return 0;
}当然，也能从下往上进行动态规划。
最长上升子序列
DP做法
895. 最长上升子序列 - AcWing题库
给定一个长度为 N 的数列a，求数值严格单调递增的子序列的长度最长是多少。
首先分析 状态表示：f(i)表示所有以a[i]结尾的上升子序列的集合长度，我们要它的最大值。
然后分析 状态计算，集合f(i)可划分为（即如何只需一步得到f[i, j]）：
- 没有上一个符合条件的元素，
f(i) = 1； - 上一个符合条件的元素是
a[j]，其中j <= i - 1，j可能有多个，那么f(i) = max(f(j) + 1)；
时间复杂度为
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a (n + 5, 0);
for (int i = 1; i <= n; ++i)
cin >> a[i];
vector<int> dp(n + 5, 0);
for (int i = 1; i <= n; ++i)
{
// 没有上一个符合条件的元素
dp[i] = 1;
// 上一个符合条件的元素是a[j]
for (int j = 1; j < i; ++j)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
}
// 遍历找答案
int ans = 0;
for (int i = n; i >= 1; --i)
ans = max(ans, dp[i]);
cout << ans;
return 0;
}如果需要输出方案是什么，可再开个数组data[]存储转移到当前状态的上一个状态：
vector<int> dp(n + 5, 0), data(n + 5, 0);
for (int i = 1; i <= n; ++i)
{
// 没有上一个符合条件的元素
dp[i] = 1;
data[i] = 0;
// 上一个符合条件的元素是a[j]
for (int j = 1; j < i; ++i)
if (a[j] < a[i])
{
dp[i] = max(dp[i], dp[j] + 1);
data[i] = j;
}
}
// 找答案在dp的哪个下标
int k = i;
for (int i = 1; i <= n; ++i)
if (f[k] < f[i])
k = i;
// dp结束后, 只需遍历data数组就能得到方案的逆序
int length = f[k];
for (int i = 0; i < length; ++i)
{
cout << a[k] << " ";
k = data[k];
}贪心优化
896. 最长上升子序列 II - AcWing题库
上面1~...的最长上升子序列的结尾，注意要最小的，只有这样增长子序列的可能性才会大。可以发现，长度为1~...的最长上升子序列的结尾一定是单增的，利用这个性质，可以在求以a[i]为结尾的最长上升子序列时，在长度为1~...的序列中二分查找，找到>= a[i]的第一个数，将a[i]插入到这里。
这是贪心算法，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
int main()
{
int n;
cin >> n;
vector<int> a(n, 0);
for (int i = 0; i < n; ++i)
cin >> a[i];
// 维护长度为1~len的最长上升子序列的结尾
int len = 0;
vector<int> q(n, 0);
q[0] = -INF;
for (int i = 0; i < n; ++i)
{
// 贪心 找到要插入a[i]的位置
int pos = lower_bound(q.begin(), q.begin() + len, a[i]) - q.begin();
if (len == pos)
q[len++] = a[i];
else
q[pos] = a[i];
}
cout << len;
}最长公共子序列
897. 最长公共子序列 - AcWing题库
给定两个字符串A，B，求这两个字符串的最长公共子序列。
首先分析 状态表示：
由于要描述两个序列，因此用二维表示f[i, j]。它的含义是 所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的公共子序列，我们要求这个公共子序列长度的最大值。
然后分析 状态计算：
可以将 A[i]和B[j]是否包含在子序列当中 作为标准划分集合f[i, j]（即如何只需一步得到f[i, j]）：
- “00”，均不在子序列中，
f[i, j] = f[i - 1, j - 1]； - “01”，
b[j]在子序列中，f[i, j] = f[i - 1, j]； - “10”，
a[i]在子序列中，f[i, j] = f[i, j - 1]； - “11”，都在子序列中，
f[i, j] = f[i - 1, j - 1] + 1；
需要注意的是，这里有重复计数，如f[i - 1, j]是包含“01”这种情况，而不是等于这种情况（因为无法直接计算”01”这种情况，只能用f[i - 1, j]的最大值来代替这种情况的最大值），如果不是求最值而是求方案数的话，这种子问题划分方法就不能用了。
我们又发现，f[i - 1, j]是包含f[i - 1, j - 1]这种情况的，因此“00”可以不用写。最终我们只需求“01”，“10”，“11”的最大值就行。
参考代码如下：
int main()
{
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
vector<vector<int>> dp(n + 5, vector<int>(m + 5, 0));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
// 先统计01和10
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
// 再看看有没有符合条件的11
if (a[i - 1] == b[j - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
cout << dp[n][m];
}编辑距离
902. 最短编辑距离 - AcWing题库
首先分析 状态表示：f[i, j]，表示所有将a[1~i]变成b[1~j]的操作次数。我们要求它的最小值。
然后分析 状态计算，集合f[i, j]可由如下操作得到：
- 通过“删除”操作得到
f[i, j]：把a[i]删掉，让a[1 ~ i-1]与b[1 ~ j]匹配（前提是它俩已经匹配了，就差删a[i]了）。那么有f[i, j] = f[i - 1, j] + 1。 - 通过“插入”操作得到
f[i, j]：在a[i]后新增字母b[j]，让a[1 ~ i]与b[1 ~ j]匹配（前提是a[1 ~ i-1]已经和b[i, j]匹配了）。那么有f[i, j] = f[i, j - 1] + 1。 - 通过“替换”操作得到
f[i, j]：把a[i]替换为b[j]，让a[1 ~ i]与b[1 ~ j]匹配。若替换前已经相等，就不用替换了；若替换前不相等，就进行替换（前提是a[1 ~ i-1]已经和b[1, j-1]相等了）。那么有f[i, j] = f[i - 1, j - 1] + 1 or 0。
最后的f[i, j]为这三种情况的最小值。
参考代码如下：
int n, m;
string a, b;
cin >> n >> a >> m >> b;
vector<vector<int>> dp(n + 5, vector<int>(m + 5, 0));
// 初始化全部需要插入操作的dp
for (int j = 0; j <= m; ++j)
dp[0][j] = j;
// 初始化全部需要删除操作的dp
for (int i = 0; i <= n; ++i)
dp[i][0] = i;
// 然后仅考虑替换操作的dp就行了
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
// 插入/删除操作已经算好了
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
// 替换操作(字符串0起点)
if (a[i - 1] == b[j - 1])
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];应用题：899. 编辑距离 - AcWing题库
要求多个字符串n和多个询问m之间的最短编辑距离，用上面
int getDist(vector<vector<int>>& dp, const string& str, const string& query)
{
int n = str.size(), m = query.size();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
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] + (str[i - 1] != query[j - 1]));
}
return dp[n][m];
}
int main()
{
// 加快输入输出速度
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> strs(n);
for (int i = 0; i < n; ++i)
cin >> strs[i];
// 为加快速度, dp仅需初始化一次
vector<vector<int>> dp(n + 5, vector<int>(m + 5, 0));
for (int j = 0; j <= m; ++j)
dp[0][j] = j;
for (int i = 0; i <= n; ++i)
dp[i][0] = i;
for (int i = 0; i < m; ++i)
{
string query;
int limit;
cin >> query >> limit;
int ans = 0;
for (int j = 0; j < n; ++j)
if (getDist(dp, strs[j], query) <= limit)
++ans;
cout << ans << '\n';
}
}练习题
最长公共子序列（LCS）
1143. 最长公共子序列 - 力扣（LeetCode）
原题。
583. 两个字符串的删除操作 - 力扣（LeetCode）
首先求出两个字符串的LCS，然后用两字符串长度和减去两倍的LCS长度即可。
int minDistance(string word1, string word2) {
// 求LCS
int n = word1.size(), m = word2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
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 (word1[i - 1] == word2[j - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
return (n - dp[n][m]) + (m - dp[n][m]);
}712. 两个字符串的最小ASCII删除和 - 力扣（LeetCode）
首先求出拥有最大ASCII删除和的LCS，然后通过减法便能得到两个字符串的最小ASCII删除和。
int minimumDeleteSum(string s1, string s2) {
// 求LCS的ASCII值
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
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 (s1[i - 1] == s2[j - 1])
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1] + s2[j - 1]);
}
int ans = 0;
for (auto ch : s1)
ans += ch;
for (auto ch : s2)
ans += ch;
return ans - dp[n][m];
}72. 编辑距离
97. 交错字符串
115. 不同的子序列
1035. 不相交的线 1806
1458. 两个子序列的最大点积 1824
1092. 最短公共超序列 1977
1639. 通过给定词典构造目标字符串的方案数 2082
44. 通配符匹配
10. 正则表达式匹配
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。最长递增子序列（LIS）
300. 最长递增子序列
673. 最长递增子序列的个数
2826. 将三个组排序 1721
1671. 得到山形数组的最少删除次数 1913
1964. 找出到每个位置为止最长的有效障碍赛跑路线 1933
2111. 使数组 K 递增的最少操作次数 1941
1626. 无矛盾的最佳球队 2027
354. 俄罗斯套娃信封问题（二维 LIS）
1691. 堆叠长方体的最大高度 2172
960. 删列造序 III 2247
2407. 最长递增子序列 II 2280
1187. 使数组严格递增 2316
1713. 得到子序列的最少操作次数 2351
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。其他一维
2944. 购买水果需要的最少金币数 1709
2140. 解决智力问题 1709
983. 最低票价 1786
2901. 最长相邻不相等子序列 II 1899
871. 最低加油次数 2074
2896. 执行操作使两个字符串相等 2172
2167. 移除所有载有违禁货物车厢所需的最少时间 2219
2188. 完成比赛的最少时间 2315
1259. 不相交的握手（会员题）
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。特殊子序列
2501. 数组中最长的方波 1480
1218. 最长定差子序列 1597
1027. 最长等差数列 1759
873. 最长的斐波那契子序列的长度 1911
446. 等差数列划分 II - 子序列
1048. 最长字符串链
3098. 求出所有子序列的能量和 2553
§7.3 矩阵快速幂优化
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。矩阵快速幂优化
部分题目由于数据范围小，也可以用线性 DP。
70. 爬楼梯
509. 斐波那契数
1137. 第 N 个泰波那契数
1220. 统计元音字母序列的数目
552. 学生出勤记录 II
790. 多米诺和托米诺平铺
2851. 字符串转换 2858
2912. 在网格上移动到目的地的方法数（会员题）
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。多维
2400. 恰好移动 k 步到达某一位置的方法数目 1751
2370. 最长理想子序列 1835
1269. 停在原地的方案数 1854
3122. 使矩阵满足条件的最少操作次数 1905
576. 出界的路径数
403. 青蛙过河
1223. 掷骰子模拟 2008
1320. 二指输入的的最小距离 2028
1575. 统计所有可行路径 2055
2318. 不同骰子序列的数目 2090
2088. 统计农场中肥沃金字塔的数目 2105
2209. 用地毯覆盖后的最少白色砖块 2106
1444. 切披萨的方案数 2127
1420. 生成数组 2176
629. K 个逆序对数组
1866. 恰有 K 根木棍可以看到的排列数目 2333
2312. 卖木头块 2363
887. 鸡蛋掉落 2377
1884. 鸡蛋掉落-两枚鸡蛋
1388. 3n 块披萨 2410
1900. 最佳运动员的比拼回合 2455
1883. 准时抵达会议现场的最小跳过休息次数 2588 避免浮点运算的技巧
LCP 57. 打地鼠
256. 粉刷房子（会员题）
265. 粉刷房子 II（会员题）
568. 最大休假天数（会员题）
1692. 计算分配糖果的不同方式（会员题）
2143. 在两个数组的区间中选取数字（会员题）
作者：灵茶山艾府
链接：https://leetcode.cn/circle/discuss/tXLS3i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。