线性动态规划与序列模型 (Linear DP)¶
线性动态规划是所有动态规划的基石。其状态沿着排布在单向时间轴或空间轴上的序列（一维或二维矩阵）线性推进，状态间的转移依赖具有天然的无后效性与拓扑偏序。
1. 最长递增子序列 (LIS)¶
给定一个长度为 \(N\) 的无序序列 \(A\)，找出其中长度最长的严格单调递增子序列。
1.1 朴素动态规划法 (O(N^2))¶
- 状态定义：\(dp[i]\) 表示以元素 \(A[i]\) 结尾的最长严格递增子序列的长度；
- 状态转移：对于所有满足 \(j < i\) 且 \(A[j] < A[i]\) 的前驱下标：
- 全局答案：\(\max_{0 \le i < n} dp[i]\)。
1.2 贪心 + 二分查找优化 (O(N log N))¶
要使递增子序列尽可能长，核心贪心原则是：长度相同的递增子序列，末尾元素越小越好（末尾越小，后续元素越容易接在它后面）。
贪心数组不变式证明¶
维护数组 \(tails[k]\)：表示长度为 \(k\) 的所有递增子序列中，末尾元素的最小值。
- 单调性定理：数组 \(tails\) 必然严格单调递增。若存在 \(k_1 < k_2\) 使得 \(tails[k_1] \ge tails[k_2]\)，则长度为 \(k_2\) 的子序列必有一个前缀长度为 \(k_1\) 且末尾元素严格小于 \(tails[k_2] \le tails[k_1]\)，与 \(tails[k_1]\) 的最小值定义矛盾。
- 遍历更新机制：遍历序列中的每个数 \(x\)：
- 在有序数组 \(tails\) 中使用
std::lower_bound查找首个 \(\ge x\) 的位置 \(it\)； - 若找不到（即 \(x\) 严格大于 \(tails\) 中所有元素），说明 \(x\) 可以扩展出更长的递增序列，直接追加：
tails.push_back(x)； - 若找到，设其下标为 \(idx\)，说明以更小的代价 \(x\) 替换掉原有的 \(tails[idx]\)：
tails[idx] = x。 - 最终 \(tails.size()\) 即为最长递增子序列的长度。
#include <vector>
#include <algorithm>
int length_of_lis(const std::vector<int>& nums) {
if (nums.empty()) return 0;
std::vector<int> tails;
for (int x : nums) {
auto it = std::lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
tails.push_back(x);
} else {
*it = x;
}
}
return tails.size();
}
- 时间复杂度：\(\mathcal{O}(N \log N)\)
- 空间复杂度：\(\mathcal{O}(N)\)
- 非降子序列拓展：若求非递减子序列（允许相等），只需将
lower_bound替换为upper_bound。
2. 最长公共子序列 (LCS)¶
给定两个字符串 \(S\)（长度为 \(m\)）和 \(T\)（长度为 \(n\)），求它们的最长公共子序列长度。
状态定义与转移¶
- 定义 \(dp[i][j]\) 表示 \(S[0 \dots i-1]\) 与 \(T[0 \dots j-1]\) 的最长公共子序列长度：
空间滚动优化¶
由于 \(dp[i][j]\) 仅取决于当前行和上一行，使用大小为 \(2 \times (n + 1)\) 的滚动数组或一维数组加临时变量可将辅助空间降至 \(\mathcal{O}(\min(m, n))\)。
#include <string>
#include <vector>
#include <algorithm>
int longest_common_subsequence(const std::string& text1, const std::string& text2) {
int m = text1.size(), n = text2.size();
std::vector<int> dp(n + 1, 0);
for (int i = 1; i <= m; ++i) {
int prev = 0; // 记录上一轮的 dp[i-1][j-1]
for (int j = 1; j <= n; ++j) {
int temp = dp[j];
if (text1[i - 1] == text2[j - 1]) {
dp[j] = prev + 1;
} else {
dp[j] = std::max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
3. 编辑距离 (Edit Distance)¶
给定两个单词 \(word1\) 和 \(word2\)，计算将 \(word1\) 转换成 \(word2\) 所使用的最少操作数。允许的操作：插入一个字符、删除一个字符、替换一个字符。
状态定义与三大转移方向¶
定义 \(dp[i][j]\) 为 \(word1[0 \dots i-1]\) 转换为 \(word2[0 \dots j-1]\) 的最少操作次数：
- 边界条件：\(dp[i][0] = i\)（全部删除），\(dp[0][j] = j\)（全部插入）；
- 转移推导：
- 若 \(word1[i - 1] == word2[j - 1]\)：末尾字符相同，无需任何代价：\(dp[i][j] = dp[i - 1][j - 1]\)；
- 若字符不同，三种操作取最小值：
- 删除 \(word1[i-1]\)：对应 \(dp[i - 1][j] + 1\)；
- 插入 \(word2[j-1]\)：对应 \(dp[i][j - 1] + 1\)；
- 替换 \(word1[i-1]\) 为 \(word2[j-1]\)：对应 \(dp[i - 1][j - 1] + 1\)。
int min_distance(const std::string& word1, const std::string& word2) {
int m = word1.size(), n = word2.size();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
}
}
}
return dp[m][n];
}
- 时间复杂度：\(\mathcal{O}(m \cdot n)\)
- 空间复杂度：\(\mathcal{O}(m \cdot n)\)（可优化至 \(\mathcal{O}(n)\)）
4. 最大子数组和与极值模型 (Kadane 算法)¶
4.1 最大子数组和 (Kadane)¶
- 状态转移：\(dp[i]\) 表示以元素 \(A[i]\) 结尾的最大连续子数组和。
- \(dp[i] = \max(A[i], dp[i - 1] + A[i])\)
- 空间压缩：当前和小于 0 时直接归零重新开始累计，时空复杂度分别为 \(\mathcal{O}(N)\) 和 \(\mathcal{O}(1)\)。
4.2 乘积最大子数组 (LeetCode 152)¶
乘法具有“负负得正”的非单调翻转特性。
- 双状态维护：同时维护以当前数结尾的最大乘积 \(max\_f\) 与最小乘积 \(min\_f\)；
- 当遇到负数时，两者的最值角色颠倒交换；
- 转移方程：
5. 股票买卖全系列状态机 DP (Unified Stock State Machine)¶
股票买卖系列是状态机 DP 的绝佳模板。所有复杂变种（手续费、冷冻期、最多 \(K\) 次交易）均能统一在状态机框架下推导。
状态空间建模¶
在每一天结束时，账户必定处于以下两类基本状态之一：
- \(hold[k]\)：当前持有股票，且这是第 \(k\) 次买入交易；
- \(free[k]\)：当前空仓（未持有股票），且已完成 \(k\) 次完整买卖交易。
统一状态转移方程 (最多 K 次交易)¶
- 买入转移：\(hold[k] = \max(hold[k], free[k - 1] - price)\)
- 卖出转移：\(free[k] = \max(free[k], hold[k] + price - fee)\)
- 冷冻期处理：若卖出后有一天的冷冻期，则买入转移所依赖的空仓状态退回为两天前的空仓状态 \(free_{i-2}\)。
6. LeetCode 经典真题精选与题解提示¶
-
LeetCode 300 - 最长递增子序列 (Longest Increasing Subsequence)
中等提示
贪心 + 二分经典模板。
- 维护长度为 \(k\) 的递增子序列末尾最小值 \(tails\) 数组。
- 遍历每个数，用
std::lower_bound寻找首个大于等于它的位置进行贪心替换；若全部小于它则追加到末尾。严格 \(\mathcal{O}(N \log N)\)。
-
LeetCode 354 - 俄罗斯套娃信封问题 (Russian Doll Envelopes)
困难提示
二维排序 Trick 转化为 LIS。
- 信封宽为 \(w\)，高为 \(h\)。
- 核心排序规则：按宽度 \(w\) 升序排列；当宽度 \(w\) 相同时，按高度 \(h\) 降序排列！
- 排序后，对高度数组 \(h\) 跑标准 LIS。为何高度降序？因为相同宽度的信封不可嵌套，降序确保了相同宽度的信封至多只能被选取一个！
-
LeetCode 1143 - 最长公共子序列 (Longest Common Subsequence)
中等提示
双序列二维 DP 基准题。
- 字符相同取对角线 \(+1\)，字符不同取左与上的最大值。
- 使用一维数组配合
prev记录对角线变量，实现空间 \(\mathcal{O}(\min(m, n))\) 压缩。
-
LeetCode 72 - 编辑距离 (Edit Distance)
中等提示
二维字符编辑状态机。
- 增、删、改三种操作对应网格图中的左移、上移与对角线转移。
- 注意空字符串边界初始化的赋值：\(dp[i][0] = i\) 与 \(dp[0][j] = j\)。
-
LeetCode 53 - 最大子数组和 (Maximum Subarray)
中等提示
Kadane 算法标杆。
- 若当前累加和小于 0，对后续元素只会产生负贡献，果断归零。动态维护历史全局最大值。
-
LeetCode 152 - 乘积最大子数组 (Maximum Product Subarray)
中等提示
正负双极值状态机。
- 遇到负数使得最大值变最小值，最小值变最大值。遇到负数直接交换两个维护变量
swap(max_val, min_val)，然后同步乘上当前数并与自身取最值。
- 遇到负数使得最大值变最小值，最小值变最大值。遇到负数直接交换两个维护变量
-
LeetCode 188 - 买卖股票的最佳时机 IV (Best Time to Buy and Sell Stock IV)
困难提示
通用 K 次交易状态机。
- 当 \(k \ge n / 2\) 时退化为无限次交易贪心累计所有正差值；
- 当 \(k < n / 2\) 时开辟长度为 \(k+1\) 的
buy与sell数组交替滚动转移。
-
LeetCode 446 - 等差数列划分 II - 子序列 (Arithmetic Slices II - Subsequence)
困难提示
以元素位置与公差为状态的哈希表动态规划。
- 设 \(f[i][d]\) 表示以 \(nums[i]\) 结尾、公差为 \(d\) 的弱等差子序列（长度 \(\ge 2\)）个数；
- 枚举前驱节点 \(j < i\)，公差 \(d = (long long)nums[i] - nums[j]\)；
- \(f[i][d] += (f[j][d] + 1)\)；其中 \(f[j][d]\) 是长度 \(\ge 3\) 的合法等差子序列数量（累加进全局答案），而额外的 \(+1\) 对应新增长度为 2 的数对 \((nums[j], nums[i])\)；
- 外层数组、内层哈希表
vector<unordered_map<long long, int>>在 \(\mathcal{O}(N^2)\) 内搞定。
-
LeetCode 1425 - 带限制的子序列和 (Constrained Subsequence Sum)
困难提示
单调队列优化线性 DP 经典标杆。
- 状态转移方程：\(dp[i] = nums[i] + \max(0, \max_{i - k \le j < i} dp[j])\)；
- 决策集合是一个长度为 \(k\) 的滑动窗口，利用单调双端队列维护窗口内的最大值，将朴素 \(\mathcal{O}(N \cdot k)\) 优化至严格 \(\mathcal{O}(N)\)。