线性 DPCSP-S

目录

💡 核心思想

线性 DP 是最基础的动态规划形式，状态沿着线性序列递推。经典问题包括：最长递增子序列（LIS）、最长公共子序列（LCS）、数字三角形等。状态转移只在相邻的有限个位置之间发生。

线性 DP 的核心是定义好"状态"。以 LIS 为例，$dp[i]$ 表示以 $a[i]$ 结尾的 LIS 长度，那么 $dp[i] = \max_{j < i, a[j] < a[i]}(dp[j]) + 1$。这个定义"以 i 结尾"非常关键——它确保了子结构性质。很多同学状态定义错了，后面怎么推都不对。

🎯 直觉理解

线性 DP 就像在一条路上走，每走一步你都记住"走到这里的最优结果"。你只需要看前面几步的结果就能决定这一步怎么走，不需要记住全部历史。

📝 算法流程

  1. 定义状态：明确 dp[i] 的含义
  2. 写出状态转移方程
  3. 确定初始条件和遍历顺序
  4. LIS 优化：用二分维护递增序列，$O(n\log n)$

$$LIS: dp[i] = \max_{j < i, a[j] < a[i]}(dp[j]) + 1$$

📊 复杂度分析

指标复杂度
时间朴素 $O(n^2)$，LIS 优化 $O(n\log n)$
空间$O(n)$

💻 参考实现（C++）

C++ (C++17)
#include <bits/stdc++.h>
using namespace std;
// LIS O(n log n) 优化
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<int> tails; // tails[i] = 长度为 i+1 的 LIS 的最小末尾
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    cout << tails.size() << endl;
    return 0;
}

⚠️ 常见坑点

LIS 的 tails 数组内容不是实际的 LIS 序列

LCS 的二维 DP 空间可能很大

状态定义不清晰导致转移方程写错

LIS 用 upper_bound 还是 lower_bound 取决于是否严格递增

📚 相关题目

题目来源难度备注
P1020 导弹拦截洛谷CSP-SLIS经典
P1439 最长公共子序列洛谷CSP-SLCS模板