子序列问题不像子数组那样要求连续，所以我们选数时得带着'往回看'的思维。LIS（最长递增子序列）是最经典的模板，很多变种都是由它衍生出来的。状态定义往往是 dp[i] 表示以 i 位置结尾的最优解；转移的时候因为允许跳过元素，通常需要一个双层循环 for i { for j < i }。但如果遇到一个数确定不了规律（比如等差、斐波那契），就可以直接升维到 dp[i][j] 表示以 i 和 j 结尾的状态。
最长递增子序列 (LIS)
题目链接：300. 最长递增子序列，找最长严格递增子序列的长度，比如 [10,9,2,5,3,7,101,18] 答案是 4（[2,3,7,101]）。
dp[i] 的含义就是必须以 nums[i] 结尾的最长递增子序列长度。怎么算？对于每个 i，往前扫一遍 j，只要 nums[j] < nums[i]，就可以接在 j 后面，我们就拿 dp[j] + 1 去更新 dp[i]。初始值都是 1，因为单独一个元素也算。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int ret = 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);
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};
这道题有更高效的 O(n log n) 贪心+二分法，但那个留到贪心专题再聊；先用 DP 把模型搞透，后面很多变种还要靠它。
摆动序列
题目链接：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 的起点。