跳转至

线性动态规划与序列模型 (Linear DP)

线性动态规划是所有动态规划的基石。其状态沿着排布在单向时间轴或空间轴上的序列（一维或二维矩阵）线性推进，状态间的转移依赖具有天然的无后效性与拓扑偏序。

1. 最长递增子序列 (LIS)

给定一个长度为 \(N\) 的无序序列 \(A\)，找出其中长度最长的严格单调递增子序列。

1.1 朴素动态规划法 (\(\mathcal{O}(N^2)\))

  • 状态定义：\(dp[i]\) 表示以元素 \(A[i]\) 结尾的最长严格递增子序列的长度；
  • 状态转移：对于所有满足 \(j < i\) 且 \(A[j] < A[i]\) 的前驱下标：
\[ dp[i] = \max_{0 \le j < i, A[j] < A[i]} (dp[j]) + 1 \]
  • 全局答案：\(\max_{0 \le i < n} dp[i]\)。

1.2 贪心 + 二分查找优化 (\(\mathcal{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] = \begin{cases} dp[i - 1][j - 1] + 1, & \text{if } S[i - 1] == T[j - 1] \\ \max(dp[i - 1][j], dp[i][j - 1]), & \text{if } S[i - 1] \neq T[j - 1] \end{cases} \]

空间滚动优化

由于 \(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\)。
\[ dp[i][j] = 1 + \min(dp[i - 1][j], \min(dp[i][j - 1], dp[i - 1][j - 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\)；
  • 当遇到负数时，两者的最值角色颠倒交换；
  • 转移方程：
\[ \begin{aligned} max\_f[i] &= \max(A[i], \max(max\_f[i - 1] \cdot A[i], min\_f[i - 1] \cdot A[i])) \\ min\_f[i] &= \min(A[i], \min(max\_f[i - 1] \cdot A[i], min\_f[i - 1] \cdot A[i])) \end{aligned} \]

5. 股票买卖全系列状态机 DP (Unified Stock State Machine)

股票买卖系列是状态机 DP 的绝佳模板。所有复杂变种（手续费、冷冻期、最多 \(K\) 次交易）均能统一在状态机框架下推导。

状态空间建模

在每一天结束时，账户必定处于以下两类基本状态之一：

  1. \(hold[k]\)：当前持有股票，且这是第 \(k\) 次买入交易；
  2. \(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 经典真题精选与题解提示