动态规划专题：子序列问题与 LIS 模型

(注：这道题有 O(NlogN) 的贪心 + 二分据解法，但那是贪心专题的内容，这里专注 DP)

三、摆动序列 (Medium)

3.1 题目描述

题目链接：376. 摆动序列

描述：差值正负交替。求最长子序列长度。

示例：输入 [1,7,4,9,2,5]，输出 6 (差值：+6, -3, +5, -7, +3)

3.2 状态定义：波峰与波谷

我们不仅要知道长度，还要知道结尾是升还是降，才能决定下一个数怎么接。

• f[i]：以 i 结尾，且最后一步是 上升 的最长摆动序列。
• g[i]：以 i 结尾，且最后一步是 下降 的最长摆动序列。

3.3 代码实现

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        // 初始化为 1
        vector<int> f(n, 1), g(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    // 此时是上升，接在之前的下降 g[j] 后面
                    f[i] = max(f[i], g[j] + 1);
                } else if (nums[j] > nums[i]) {
                    // 此时是下降，接在之前的上升 f[j] 后面
                    g[i] = max(g[i], f[j] + 1);
                }
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

(注：此题 O(N) 贪心解法更优，但 DP 解法有助于理解状态机思想)

四、最长递增子序列的个数 (Medium)

4.1 题目描述

题目链接：673. 最长递增子序列的个数

描述：同样是 LIS，这次要问：长度等于 LIS 的子序列一共有几个？

4.2 双重状态

只记录长度不够了，还要记录个数。

• len[i]：以 i 结尾的最长长度。
• count[i]：以 i 结尾的最长长度的方案数。

转移逻辑：当 nums[j] < nums[i] 时：

1. 如果 len[j] + 1 > len[i]：说明找到了一个更长的序列。更新 len[i]，并且 count[i]重置为 count[j]。
2. 如果 len[j] + 1 == len[i]：说明找到了一个长度一样长的序列。len[i] 不变，但 count[i]累加count[j]。

4.3 代码实现

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1), count(n, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 > len[i]) {
                        // 发现更长的，重置
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    } else if (len[j] + 1 == len[i]) {
                        // 长度相同，累加方案数
                        count[i] += count[j];
                    }
                }
            }
            maxLen = max(maxLen, len[i]);
        }
        // 统计所有达到 maxLen 的个数
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (len[i] == maxLen) ret += count[i];
        }
        return ret;
    }
};

五、最长数对链 (Medium)

5.1 题目描述

题目链接：646. 最长数对链

描述：[a, b] 后面能接 [c, d] 当且仅当 b < c。求最长链。

5.2 预处理：排序

这题简直就是 LIS 的翻版。唯一的区别是：数组可能是乱序的。所以第一步：根据第一个元素排序。然后就是标准的 LIS 模板：if pairs[j][1] < pairs[i][0]，则接上。

5.3 代码实现

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        // 关键步骤：排序
        sort(pairs.begin(), pairs.end());
        int n = pairs.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

六、最长定差子序列 (Medium)

6.1 题目描述

题目链接：1218. 最长定差子序列

描述：求差值固定为 difference 的最长子序列。arr.length <= 10^5。

6.2 优化：Hash Map

如果还用双层循环 O(N²)，在这道题 10^5 的数据量下会超时。关键点：这题的差是固定的！对于 x = arr[i]，我们要找的前一个数必然是 x - difference。我们可以用哈希表 hash[val] 记录以 val 结尾的最长长度。状态转移变成 O(1)：hash[x] = hash[x - diff] + 1。

6.3 代码实现

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> hash; // val -> length
        int ret = 1;
        for (int x : arr) {
            // 直接查找前一个数是否存在
            hash[x] = hash[x - difference] + 1;
            ret = max(ret, hash[x]);
        }
        return ret;
    }
};

七、最长的斐波那契子序列的长度 (Medium)

7.1 题目描述

题目链接：873. 最长的斐波那契子序列的长度

描述：找最长的子序列，满足 x_i + x_{i+1} = x_{i+2}。

7.2 升维：双指针 DP

一个数确定不了斐波那契数列，两个数才能确定。

• 状态：dp[i][j] 表示以 i 和 j (i < j) 结尾的斐波那契子序列长度。
• 转移：nums[j] 是当前数，nums[i] 是前一个数。我们要找前前一个数 target = nums[j] - nums[i]。如果能找到这个 target (下标为 k)，那么：dp[i][j] = dp[k][i] + 1。

优化：用哈希表预存 Value -> Index 的映射，方便快速找 k。

7.3 代码实现

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        // 值 -> 下标 映射
        unordered_map<int, int> idxMap;
        for (int i = 0; i < n; i++) idxMap[arr[i]] = i;
        // dp[i][j] 以 i, j 结尾
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 0;
        // 先固定 j (最后一个数)
        for (int j = 2; j < n; j++) {
            // 再枚举 i (倒数第二个数)
            for (int i = 1; i < j; i++) {
                int target = arr[j] - arr[i];
                // 如果 target 存在，且在 i 之前
                if (target < arr[i] && idxMap.count(target)) {
                    int k = idxMap[target];
                    dp[i][j] = dp[k][i] + 1;
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret < 3 ? 0 : ret;
    }
};

八、最长等差数列 (Medium)

8.1 题目描述

题目链接：1027. 最长等差数列

描述：求最长的等差子序列长度。公差不固定。

8.2 思路

和斐波那契几乎一样，两个数确定公差。

• 状态：dp[i][j] 以 i, j 结尾的等差数列长度。
• 公差：diff = nums[j] - nums[i]。
• 前一个数：target = nums[i] - diff。

这题可以直接存下标，也可以在遍历过程中动态维护 Hash。

8.3 代码实现

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        // dp[i][j] 表示以 i 和 j 结尾
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        // 为了加速找 k，可以用 map 存
        // 但这题数据范围小，也可以遍历，或者边走边存
        // 既然已经 O(N^2)，最内层最好是 O(1)
        // 这里用一个 map 数组，indexMap[x] 表示值为 x 的下标
        // 实际上这题可以直接枚举公差，或者用 nums[i] 的值域做 hash
        // 下面是标准双指针解法，配合 hash 优化
        // 值 -> 下标
        // 注意：因为有重复元素，我们要在遍历过程中动态更新 hash
        unordered_map<int, int> hash;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int target = 2 * nums[i] - nums[j]; // nums[i] - (nums[j] - nums[i])
                if (hash.count(target)) {
                    int k = hash[target];
                    dp[i][j] = dp[k][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            // 关键：遍历完 i 之后，才把 i 放入 hash
            // 这样保证取到的 k 一定在 i 之前
            hash[nums[i]] = i;
        }
        return ret;
    }
};

九、等差数列划分 II - 子序列 (Hard)

9.1 题目描述

题目链接：446. 等差数列划分 II - 子序列

描述：求等差子序列的个数。

9.2 状态定义与累加

• 状态：dp[i][j] 以 i, j 结尾的等差数列个数。
• 转移：找到 k 后，dp[i][j] += dp[k][i] + 1。为什么要 +1？dp[k][i] 是以 k, i 为结尾的，加上 j 构成了 ... k, i, j，这些都是旧的序列延长。+1 是指 k, i, j 这三个数新构成的一个长度为 3 的序列。
• 注意：因为是求个数，可能有多个相同的 k，所以哈希表要存下标列表 List<Integer>。

9.3 代码实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        // dp[i][j] 以 i, j 结尾的等差数列个数
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // 优化：值 -> 下标列表
        unordered_map<long long, vector<int>> map;
        for (int i = 0; i < n; i++) map[nums[i]].push_back(i);
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                long long target = 2LL * nums[i] - nums[j];
                if (map.count(target)) {
                    for (int k : map[target]) {
                        if (k < i) {
                            // 累加个数
                            dp[i][j] += dp[k][i] + 1;
                        } else {
                            break; // 因为 map 里下标是递增的
                        }
                    }
                }
                ans += dp[i][j];
            }
        }
        return (int)ans;
    }
};

十、总结

总结：子序列问题的核心在于不连续。

1. LIS 模型：dp[i] 依赖 dp[0...i-1]，双层循环。
2. 定值确定性：如果一个数能确定（如定差），用哈希表优化到 O(N)。
3. 两数确定性：如果需要两个数确定规律（斐波那契、等差），升维到二维 DP dp[i][j]。