子序列 DP 实战：从基础 LIS 到二维状态转移

题目链接：376. 摆动序列。给定序列，要找最长子序列，使得相邻两数之差正负交替，比如 [1,7,4,9,2,5] 可以得到长度 6。

只记录长度还不够，我们需要知道结尾的"姿势"——最后一步是涨还是跌，因为这会决定下一个数能不能接上。于是拆成两个数组：f[i] 表示以 i 结尾且最后一步是上升的最长摆动序列长度，g[i] 对应最后一步是下降的。

转移时，对于每个 j < i，如果 nums[j] < nums[i]，说明现在上升，可以接在 g[j] 后面，f[i] = max(f[i], g[j] + 1)；反过来如果 nums[j] > nums[i]，现在下降，接在 f[j] 后面，g[i] = max(g[i], f[j] + 1)。

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;
    }
};

这题也有 O(n) 的贪心，不过 DP 版本更容易套到其他类似于"需要记住上一个状态是涨还是跌"的问题里。

最长递增子序列的个数

题目链接：673. 最长递增子序列的个数。不仅要最长长度，还要问有多少个最长子序列。

显然只用一个 dp 数组不够了，需要再带一个计数数组。len[i] 还是以 i 结尾的最长长度，count[i] 是以 i 结尾的最长长度的方案数。遍历 j 时，如果 len[j] + 1 > len[i]，表示找到了更长的序列，那就更新 len[i]，并把 count[i] 置为 count[j]（替代）；如果 len[j] + 1 == len[i]，表示发现了等长的不同序列，count[i] += count[j]（累加）。最后把所有 len 等于全局最长的 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;
    }
};

最长数对链

题目链接：646. 最长数对链。输入是一对对 [a,b]，链的条件是 b < c 才能接。这题几乎就是 LIS 的翻版，唯一不同是初始顺序可能乱。

先按数对的第一个元素排个序，然后就和 LIS 一模一样了：if pairs[j][1] < pairs[i][0] 则 dp[i] = max(dp[i], dp[j] + 1)。

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;
    }
};

最长定差子序列

题目链接：1218. 最长定差子序列。这题数据量到了 10^5，再用双层循环 O(n²) 会超时。但题目给的差值 difference 是固定的，这就好办了。对于当前数字 x，我们只关心 x - difference 结尾的最长长度是多少。用一个哈希表 hash[x] 表示以 x 结尾的最长长度，那么 hash[x] = hash[x - difference] + 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;
    }
};

定差这个优化很实用，把原本 O(n²) 的 for-for 直接降成 O(n)。

最长的斐波那契子序列的长度

题目链接：873. 最长的斐波那契子序列的长度。要求子序列满足 x_i + x_{i+1} = x_{i+2}。一个数没法确定斐波那契数列，两个数才行。所以把状态升维：dp[i][j] 表示以 i 和 j（i < j）结尾的斐波那契子序列长度，初始值至少是 2。

固定 j，枚举 i，我们要找 target = arr[j] - arr[i] 且它必须在 i 之前。如果存在这样的下标 k，那么 dp[i][j] = dp[k][i] + 1。为了快速查找，预先建一个值到下标的映射。注意 target < arr[i] 这个剪枝能跳过一些不可能的数值（因为数列肯定递增）。

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;
    }
};

最长等差数列

题目链接：1027. 最长等差数列。和斐波那契一样，两个数才能定公差。dp[i][j] 表示以 i、j 结尾的等差子序列长度，初始为 2。公差 diff = nums[j] - nums[i]，前一个数应该是 target = nums[i] - diff。如果 target 出现过且下标 k 在 i 之前，就 dp[i][j] = dp[k][i] + 1。

为了避免重复元素干扰，我们可以在外循环 i 时动态维护一个哈希表，把遍历完的 i 才放进表里，这样保证取到的 k 一定在 i 之前。

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]; // 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]);
            }
            hash[nums[i]] = i;
        }
        return ret;
    }
};

等差数列划分 II - 子序列（Hard）

题目链接：446. 等差数列划分 II - 子序列。这次要求所有等差子序列的个数，不是长度。仍然用 dp[i][j]，但表示以 i、j 结尾的等差数列个数。找到 k 之后，dp[i][j] += dp[k][i] + 1（那个 +1 是 [k,i,j] 这一组新序列）。因为可能存在多个相同的 target 值，所以哈希表要存下标列表，遍历所有满足 k < i 的 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;
    }
};

最后这题有点难，但思路还是前面二维 DP 的延伸，只不过从求长度变成了求计数。

总结

子序列 DP 的核心就是'不连续'，因此经典套路是 dp[i] 回顾前面所有的 j。当单个下标定不住规律时，升维到 dp[i][j] 用两个位置来确定状态（比如等差需要确定公差，斐波那契需要确定前两个数）。遇到定差这类问题，利用哈希表直接映射可以把复杂度压到线性。这些技巧组合起来，能解决大部分线性 DP 的子序列问题。下一篇我们会进入回文串专题，那是区间 DP 的起点。