GESP 7级 · 线性DP

📖 一句话理解

给定一个数列，从中按原顺序选出一些数（不一定要连续），使得选出的数严格递增，并且长度最长。这个最长的长度就是 LIS（Longest Increasing Subsequence）。

💡 为什么重要？

LIS是线性DP的经典代表。它教会你一个重要的DP技巧：用"以某个位置结尾"来定义状态。这种思维方式在很多DP问题中都会用到（比如最长公共子序列LCS、最长回文子串等）。GESP 7级和NOIP初赛经常出LIS相关题目。

📋 前置知识

子序列的概念：从原序列中按顺序挑出一些元素组成的新序列（不需要连续）
严格递增：每个数都比前一个数大（不能相等）
for循环嵌套：双层循环的写法
max()函数：取最大值

🧠 什么是子序列？

📝 举例说明

原序列：[3, 1, 4, 1, 5, 9]

[3, 4, 5] — ✅ 是子序列（按原顺序挑出，严格递增）
[1, 4, 5, 9] — ✅ 是子序列（严格递增，长度4）
[3, 4, 1] — ❌ 不是递增的
[1, 5] — ✅ 是子序列（递增，但不是最长的）

LIS就是找出最长的那个递增子序列的长度。

📐 DP思路

状态定义（关键！）

dp[i] = 以第 i 个元素结尾的最长上升子序列的长度。

💡 为什么要"以第i个元素结尾"？

因为LIS要求递增，如果我们知道"以第i个结尾的最长长度"，那么在考虑第j个元素（j>i）时，只要 a[j] > a[i]，就能把第i个结尾的子序列延伸到第j个。
状态定义的关键是：让转移变得简单！

转移方程

📐 核心转移方程

dp[i] = 1 （初始值，至少自己一个元素）
dp[i] = max(dp[i], dp[j] + 1) ，对于所有 j < i 且 a[j] < a[i]

含义：在i之前找一个比a[i]小的a[j]，把以j结尾的子序列延伸到i

DP数组怎么来的？一步步推导

🔢 推导过程

定义dp[i]：以a[i]结尾的LIS长度
每个dp[i]至少为1：因为a[i]自己就是一个长度为1的子序列
对于每个i，往前看所有j<i：如果a[j] < a[i]，说明可以把a[i]接到以a[j]结尾的子序列后面，长度变成 dp[j]+1
取最大值：在所有能接的情况中，选最长的
最终答案：所有dp[i]中的最大值（因为LIS不一定以最后一个元素结尾）

🔢 手动推演

序列：[2, 1, 5, 3, 4]

📊 逐个推演

dp[0] = 1 （只有2自己）
dp[1] = 1 （只有1自己，1前面的2比1大，不能接）
dp[2] = 2 （5前面，1<5可以接，dp[1]+1=2）
dp[3] = 2 （3前面，1<3可以接，dp[1]+1=2；2<3也可以接，dp[0]+1=2）
dp[4] = 3 （4前面，1<4→dp[1]+1=2；3<4→dp[3]+1=3，最大）
最终答案：max(1,1,2,2,3) = 3（子序列 [1,3,4] 或 [2,3,4]）

💻 O(n²) 代码（考试最常用）

💻 完整示例代码

#include <iostream>
#include <vector>
#include <algorithm>  // max()
using namespace std;

int main() {
    int n;
    cin >> n;                  // 读入序列长度
    vector<int> a(n);          // 原序列
    for (int i = 0; i < n; i++)
        cin >> a[i];           // 读入每个元素

    // dp[i] = 以a[i]结尾的LIS长度
    vector<int> dp(n, 1);      // 初始全部为1（每个元素自身就是长度1的子序列）

    int ans = 1;               // 全局答案，至少为1

    for (int i = 1; i < n; i++) {       // 从第2个元素开始
        for (int j = 0; j < i; j++) {   // 看前面所有元素
            if (a[j] < a[i]) {         // 如果前面的元素比当前小
                // 可以把a[i]接到以a[j]结尾的子序列后面
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);          // 更新全局最大值
    }

    cout << "最长上升子序列长度: " << ans << endl;
    return 0;
}

⚡ O(n log n) 优化（进阶，了解即可）

💡 优化思路（一句话）

用一个数组 tail[]，tail[len] 存储"长度为len的上升子序列的最小末尾元素"。新元素用二分查找找到位置插入，时间从 O(n²) 降到 O(n log n)。

💻 O(n log n) 代码

#include <iostream>
#include <vector>
#include <algorithm>  // lower_bound
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    vector<int> tail;  // tail[i] = 长度为i+1的LIS的最小末尾元素

    for (int i = 0; i < n; i++) {
        // 找到第一个 >= a[i] 的位置
        auto it = lower_bound(tail.begin(), tail.end(), a[i]);
        if (it == tail.end()) {
            tail.push_back(a[i]);    // a[i]比所有都大，LIS长度+1
        } else {
            *it = a[i];               // 替换，让末尾更小（为后面留更多空间）
        }
    }

    cout << "最长上升子序列长度: " << tail.size() << endl;
    return 0;
}

🚨 易错点

⚠️ 常见错误汇总

子序列 ≠ 子串：子序列不需要连续！很多人搞混这两个概念。"子串"必须连续，"子序列"可以跳着选。
最终答案不是dp[n-1]：LIS不一定以最后一个元素结尾，答案是所有dp[i]中的最大值。
dp数组初始化为1：不是0！每个元素自身就是长度为1的子序列。
严格递增 vs 非严格递增：题目说"严格递增"就用 a[j] < a[i]，说"非严格"（可以相等）就用 a[j] <= a[i]。审题时注意！
O(n²)代码内层循环范围：j 从 0 到 i-1（不包括i），不要写成 j 从 0 到 n。

🎯 练习建议

📝 循序渐进练习路径

手推小例子：在纸上写出dp数组的完整推演过程，比如序列 [10, 9, 2, 5, 3, 7, 101]。
先掌握O(n²)：考试中n通常不超过5000，O(n²)足够。
做经典题目：
- P1020 导弹拦截（洛谷，LIS变形）
- P1233 木棍整理
- LeetCode 300 最长递增子序列
进阶变体：最长不上升子序列、最长不下降子序列，只需改比较符号。
了解O(n log n)：如果时间允许，学习贪心+二分优化版本。

← 上一个：完全背包 📖 返回主目录下一个：区间DP →

线性DP · 最长上升子序列（LIS）