动态规划专题：子序列问题深度解析
一、前言：从 O(N) 到 O(N²)
与子数组（必须连续）不同，子序列允许跳过元素。这看似简单的差异，却彻底改变了状态转移的逻辑。
核心心法：
- 状态定义：
dp[i]通常表示以i位置结尾的最长子序列长度。 - 状态转移：由于不连续，
i可以接在0到i-1之间任何一个符合条件的j后面。因此通常需要双层循环来寻找最优的j。 - 高阶技巧：如果单个数无法确定规律（如等差、斐波那契），那就定两个数，使用二维 DP
dp[i][j]表示以i和j结尾的状态。
二、最长递增子序列 (LIS)
题目描述
找到最长严格递增子序列的长度。
示例：
输入：[10,9,2,5,3,7,101,18]
输出：4 ([2,3,7,101])
核心思路
- 状态：
dp[i]表示以nums[i]结尾的最长递增子序列长度。 - 转移：站在
i位置往回看所有j(0 <= j < i)。如果nums[j] < nums[i]，说明能接在j后面。我们要选一个最长的dp[j]接上去。dp[i] = max(dp[j] + 1);
代码实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
// 初始化为 1，因为每个元素自己就是一个长度为 1 的子序列
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(NlogN) 的贪心 + 二分解法，但那是贪心专题的内容，这里专注 DP)
三、摆动序列
题目描述
差值正负交替。求最长子序列长度。
示例：
输入：[1,7,4,9,2,5]
输出：6 (差值：+6, -3, +5, -7, +3)
状态定义：波峰与波谷
我们不仅要知道长度，还要知道结尾是升还是降，才能决定下一个数怎么接。
f[i]：以i结尾，且最后一步是 上升 的最长摆动序列。g[i]：以i结尾，且最后一步是 下降 的最长摆动序列。
代码实现
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
// 初始化为 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 解法有助于理解状态机思想)
四、最长递增子序列的个数
题目描述
同样是 LIS，这次要问：长度等于 LIS 的子序列一共有几个？
双重状态
只记录长度不够了，还要记录个数。
len[i]：以i结尾的最长长度。count[i]：以i结尾的最长长度的方案数。
转移逻辑：当 nums[j] < nums[i] 时：
- 如果
len[j] + 1 > len[i]：说明找到了一个更长的序列。更新len[i]，并且count[i]重置为count[j]。 - 如果
len[j] + 1 == len[i]：说明找到了一个长度一样长的序列。len[i]不变，但count[i]累加count[j]。
代码实现
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
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;
}
};
五、最长数对链
题目描述
[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;
}
};
六、最长定差子序列
题目描述
求差值固定为 difference 的最长子序列。
arr.length <= 10^5。
优化：Hash Map
如果还用双层循环 O(N²)，在这道题 10^5 的数据量下会超时。
关键点：这题的差是固定的！对于 x = arr[i]，我们要找的前一个数必然是 x - difference。我们可以用哈希表 hash[val] 记录以 val 结尾的最长长度。状态转移变成 O(1)：hash[x] = hash[x - diff] + 1。
代码实现
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;
}
};
七、最长的斐波那契子序列的长度
题目描述
找最长的子序列，满足 x_i + x_{i+1} = x_{i+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。
代码实现
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;
}
};
八、最长等差数列
题目描述
求最长的等差子序列长度。公差不固定。
思路
和斐波那契几乎一样，两个数确定公差。
- 状态：
dp[i][j]以i,j结尾的等差数列长度。 - 公差：
diff = nums[j] - nums[i]。 - 前一个数：
target = nums[i] - diff。
这题可以直接存下标，也可以在遍历过程中动态维护 Hash。
代码实现
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 存
// 注意：因为有重复元素，我们要在遍历过程中动态更新 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 - 子序列
题目描述
求等差子序列的个数。
状态定义与累加
- 状态：
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，所以哈希表要存下标列表vector<int>。
代码实现
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>> mp;
for (int i = 0; i < n; i++) mp[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 (mp.count(target)) {
for (int k : mp[target]) {
if (k < i) {
// 累加个数
dp[i][j] += dp[k][i] + 1;
} else {
break; // 因为 map 里下标是递增的
}
}
}
ans += dp[i][j];
}
}
return (int)ans;
}
};
十、总结
子序列问题的核心在于不连续。
- LIS 模型：
dp[i]依赖dp[0...i-1]，双层循环。 - 定值确定性：如果一个数能确定（如定差），用哈希表优化到 O(N)。
- 两数确定性：如果需要两个数确定规律（斐波那契、等差），升维到二维 DP
dp[i][j]。
到这里，你已经掌握了线性 DP 中关于子序列的绝大部分套路。
