c++中如何实现最长递增子序列LIS_c++动态规划解决LIS问题

冰火之心 2026-01-08 00:00:00 次阅读

因为只有定义 dp[i] 为“以 nums[i] 结尾的最长递增子序列长度”，才能通过比较 nums[j]

为什么 dp[i] 定义成“以 nums[i] 结尾的最长递增子序列长度”才对

很多初学者会误把 dp[i] 理解为“前 i 个元素中的 LIS 长度”，但这会导致状态无法转移：你没法从 dp[i-1] 推出 dp[i]，因为新增的 nums[i] 可能接不上前面任何子序列的末尾。只有定义成“以 nums[i] 结尾”，才能明确判断：对所有 j 且 nums[j] ，尝试用 dp[j] + 1 更新 dp[i]。

这个定义让状态转移有依据，也保证每个 dp[i] 是可计算、可验证的局部最优。

标准 O(n²) 动态规划写法要注意什么

核心是两层循环 + 条件更新。容易漏掉的点：

dp 数组必须初始化为 1（每个元素自身构成长度为 1 的递增子序列）

内层循环 j 必须从 0 到 i-1，不能只看前一个

更新条件严格是 nums[j] ，不是

最终答案不是 dp[n-1]，而是整个 dp 数组的最大值
vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
int n = nums.size();
vector dp(n, 1);
for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        if (nums[j] < nums[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}
int ans = *max_element(dp.begin(), dp.end()); // ans = 4
想优化到 O(n log n)？必须换思路用贪心 + 二分

O(n²) 在 n > 10⁴ 时可能超时。lower_bound 优化的关键不是加速 DP，而是放弃记录所有可能结尾，转而维护一个数组 tail，其中 tail[len] 表示长度为 len+1 的递增子序列的最小可能末尾值。

这样做的好处：

tail 始终严格递增 → 支持二分查找

每次用 nums[i] 替换第一个 ≥ 它的 tail[k]，或追加到末尾

最终 tail.size() 就是 LIS 长度（但 tail 本身不一定是真实子序列）
vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
vector tail;
for (int x : nums) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) {
        tail.push_back(x);
    } else {
        *it = x;
    }
}
int ans = tail.size(); // ans = 4
如果需要输出任意一个 LIS，而不是只求长度

O(n²) 方法可以回溯，O(n log n) 方法也可以，但要额外维护两个数组：

dp[i]：以 i 结尾的 LIS 长度（仍需 O(n²) 计算）

prev[i]：在最优路径中，i 的前一个索引（即哪个 j 贡献了最大 dp[j]+1）

找到 dp 最大值对应的位置 idx，然后沿 prev[idx] 回溯构造结果

注意：prev 数组初始化为 -1，回溯时要逆序插入，最后反转才是正序 LIS。

真正难的不是写对算法，而是意识到：O(n log n) 版本天生不保存路径信息；要输出序列，要么接受 O(n²) 时间，要么在贪心版本里同步维护索引映射——后者代码复杂度陡增，实际项目中建议优先确认是否真需要输出子序列本身。