动态规划专题：子序列问题的核心思路与实战

题目：376. 摆动序列 求差值正负交替的最长子序列长度。

思路： 不仅要知道长度，还要知道结尾是'升'还是'降'。

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

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        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]) {
                    f[i] = max(f[i], g[j] + 1);
                } else if (nums[j] > nums[i]) {
                    g[i] = max(g[i], f[j] + 1);
                }
            }
            ret = max(ret, max(f[i], g[i]));
        }
        return ret;
    }
};

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

题目：673. 最长递增子序列的个数 求长度等于 LIS 的子序列一共有几个？

思路： 需要双重状态：

• len[i]：以 i 结尾的最长长度。
• count[i]：以 i 结尾的最长长度的方案数。 当 nums[j] < nums[i] 时，若发现更长序列则重置 count，若长度相同则累加 count。

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]);
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (len[i] == maxLen) ret += count[i];
        }
        return ret;
    }
};

四、最长数对链 (Medium)

题目：646. 最长数对链 [a, b] 后能接 [c, d] 当且仅当 b < c。

思路： 本质是 LIS 变种。先按第一个元素排序，然后套用 LIS 模板：if pairs[j][1] < pairs[i][0]。

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)

题目：1218. 最长定差子序列 求差值固定为 difference 的最长子序列。数据量可达 10^5。

思路： O(N²) 会超时。利用差值固定的特性，对于 x = arr[i]，前一个数必然是 x - difference。使用哈希表记录以某值结尾的最长长度，状态转移变为 O(1)。

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> hash;
        int ret = 1;
        for (int x : arr) {
            hash[x] = hash[x - difference] + 1;
            ret = max(ret, hash[x]);
        }
        return ret;
    }
};

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

题目：873. 最长的斐波那契子序列的长度 满足 x_i + x_{i+1} = x_{i+2}。

思路： 一个数定不了斐波那契，需要两个数。

• 状态：dp[i][j] 表示以 i 和 j 结尾的斐波那契子序列长度。
• 转移：找前前一个数 target = nums[j] - nums[i]，若存在下标 k，则 dp[i][j] = dp[k][i] + 1。 需预存 Value -> Index 映射加速查找。

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;
        
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 0;
        for (int j = 2; j < n; j++) {
            for (int i = 1; i < j; i++) {
                int target = arr[j] - arr[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)

题目：1027. 最长等差数列 求最长的等差子序列长度，公差不固定。

思路： 类似斐波那契，用两个数确定公差。

• 状态：dp[i][j] 以 i, j 结尾的等差数列长度。
• 公差：diff = nums[j] - nums[i]。
• 优化：用哈希表动态维护值为 x 的下标，避免重复计算。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        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];
                if (hash.count(target)) {
                    int k = hash[target];
                    dp[i][j] = dp[k][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }
        return ret;
    }
};

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

题目：446. 等差数列划分 II - 子序列 求等差子序列的个数。

思路：

• 状态：dp[i][j] 以 i, j 结尾的等差数列个数。
• 转移：找到 k 后，dp[i][j] += dp[k][i] + 1。
• 注意：因为可能有多个相同的 k，哈希表需存下标列表。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        long long ans = 0;
        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;
                        }
                    }
                }
                ans += dp[i][j];
            }
        }
        return (int)ans;
    }
};

总结

子序列问题的关键在于理解'不连续'带来的状态依赖变化。

1. LIS 模型：dp[i] 依赖 dp[0...i-1]，标准双层循环。
2. 定值确定性：若差值固定，用哈希表将复杂度降至 O(N)。
3. 两数确定性：若需两个数确定规律（如斐波那契、等差），升维至二维 DP dp[i][j]。

掌握这些套路，基本覆盖了线性 DP 中子序列类问题的核心模式。