一、课上练习

编程练习

1. 最长上升子序列：L3431

二、知识总结

✨ 核心思想

最长上升子序列（Longest Increasing Subsequence，简称 LIS）是动态规划中的经典问题，主要涉及在一个给定序列中寻找最长的严格递增的子序列。

需要注意的关键点：

• 子序列不要求元素在原序列中连续，但它们在原序列中的相对顺序必须保持一致
• 例如，对于序列 [10, 20, 10, 30, 40, 50]，最长上升子序列是 [10, 20, 30, 40, 50]，长度为 5

✨ 动态规划解法

状态定义

定义 dp[i] 为以第 i 个元素结尾的最长上升子序列的长度。每个元素自身可以构成长度为 1 的子序列，因此 dp[i] 至少为 1。

状态转移方程

对于每个 i（从 1 到 n），遍历 j（从 0 到 i-1）：

如果 nums[j] < nums[i]，则 nums[i] 可以接在 nums[j] 后面形成一个更长的上升子序列，因此：

dp[i] = max(dp[i], dp[j] + 1)

初始化

每个元素自成一个子序列，所以所有的 dp[i] 初始值为 1。

计算顺序

自前向后计算 dp 数组，每计算一个 dp[i]，都需要回头看前面所有的 dp[j]（j < i）。

最终结果

整个数组的最长上升子序列长度即为 dp 数组中的最大值。

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int lengthOfLIS(std::vector<int>& nums) {
6    if (nums.empty()) return 0;
7    int n = nums.size();
8    std::vector<int> dp(n, 1);
9    int max_len = 1;
10    for (int i = 1; i < n; ++i) {
11        for (int j = 0; j < i; ++j) {
12            if (nums[j] < nums[i]) {
13                dp[i] = std::max(dp[i], dp[j] + 1);
14            }
15        }
16        max_len = std::max(max_len, dp[i]);
17    }
18    return max_len;
19}
20
21int main() {
22    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
23    std::cout << "Length of LIS: " << lengthOfLIS(nums) << std::endl;
24    return 0;
25}

✨ 执行示例

以数组 nums = [10, 9, 2, 5, 3, 7, 101, 18] 为例，追踪 dp 数组的填充过程：

初始化： 所有 dp[i] = 1

最终 dp 数组： [1, 1, 1, 2, 2, 3, 4, 4]

最长上升子序列长度 = max(dp) = 4，对应的子序列为 [2, 5, 7, 101] 或 [2, 5, 7, 18] 或 [2, 3, 7, 101] 等。

✨ 解题步骤详解

解 LIS 问题的步骤：

1. 明确子序列的定义：不要求连续，但要保持原序列中的相对顺序
2. 定义 dp 数组：dp[i] = 以 nums[i] 结尾的 LIS 长度（注意是"结尾"）
3. 对每个位置 i：遍历所有 j < i，如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面
4. 取最大值：dp[i] = max(dp[j] + 1) 对所有满足条件的 j
5. 最终答案：不是 dp[n-1]，而是整个 dp 数组的最大值

✨ 常见错误

1. 误以为答案是 dp[n-1]：LIS 不一定以最后一个元素结尾，必须取 dp 数组中的最大值
2. 忘记初始化 dp 为 1：每个元素自身构成长度为 1 的子序列
3. 混淆子序列和子数组：子序列不要求元素连续，子数组（子串）要求连续
4. 严格递增 vs 非递减：注意题目要求是严格递增（<）还是非递减（<=），条件写错会导致结果不同
5. 内层循环方向错误：j 必须从 0 遍历到 i-1，确保检查 i 之前的所有元素

✨ 算法评价

• 时间复杂度：O(n²)，因为需要双层循环来计算 dp 数组
• 空间复杂度：O(n)，用于存储 dp 数组

✨ 更高效的算法

尽管上述动态规划方法在一般情况下表现良好，但存在更高效的方法可以将时间复杂度降低到 O(n log n)。这种方法结合了二分查找和动态规划，通过维护一个有序的子序列列表，并使用二分查找来确定每个数字的插入位置，从而有效地更新可能的最长上升子序列。

最长上升子序列问题不仅是动态规划的经典案例，也展示了如何通过改变思路从而极大地提高算法效率的重要性。

三、课后练习

编程练习

1. 拦截导弹：L3432