【动态规划篇】专题(六)：子序列问题——不连续的艺术

Ne0inhk

— 11 min read
【动态规划篇】专题(六)：子序列问题——不连续的艺术

文章目录

LIS 模型及其衍生：回头看，全是风景

一、 前言：从 O(N) 到 O(N²)

💬 开篇：和子数组（必须连续）不同，子序列可以跳着选。

🚀 核心心法：状态定义：dp[i] 表示以 i 位置结尾的最长子序列…状态转移：因为不连续，所以 i 可以接在 0 到 i-1 任何一个符合条件的 j 后面。因此通常需要一个双层循环。高阶技巧：如果一个数定不下规律（比如等差、斐波那契），那就定两个数（dp[i][j] 表示以 i 和 j 结尾）。

二、 最长递增子序列 (Medium)

2.1 题目描述

题目链接：300. 最长递增子序列

描述：
找到最长严格递增子序列的长度。

示例：
输入：[10,9,2,5,3,7,101,18]
输出：4 ([2,3,7,101])

2.2 核心思路：LIS 模型

  • 状态：dp[i] 表示以 nums[i]结尾的最长递增子序列长度。
  • 转移：
    我站在 i 位置，往回看所有 j (0 <= j < i)。
    如果 nums[j] < nums[i]，说明我能接在 j 后面。
    我要选一个最长的 dp[j] 接上去。
    dp[i] = max(dp[j] + 1)。

2.3 代码实现

classSolution{public:intlengthOfLIS(vector<int>& nums){int n = nums.size();// 初始化为 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)

三、 摆动序列 (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 代码实现

classSolution{public:intwiggleMaxLength(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);}elseif(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 代码实现

classSolution{public:intfindNumberOfLIS(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];}elseif(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 代码实现

classSolution{public:intfindLongestChain(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 代码实现

classSolution{public:intlongestSubsequence(vector<int>& arr,int difference){ unordered_map<int,int> hash;// val -> lengthint 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 代码实现

classSolution{public:intlenLongestFibSubseq(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 代码实现

classSolution{public:intlongestArithSeqLength(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 代码实现

classSolution{public:intnumberOfArithmeticSlices(vector<int>& nums){int n = nums.size();longlong ans =0;// dp[i][j] 以 i, j 结尾的等差数列个数 vector<vector<int>>dp(n,vector<int>(n,0));// 优化：值 -> 下标列表 unordered_map<longlong, 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++){longlong 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]。

恭喜你！到这里，你已经掌握了 线性 DP 的绝大部分套路。下一篇，我们将进入 回文串问题 —— 这是一个关于对称美学的专题，也是区间 DP 的入门课。准备好了吗？ 🚀

Read more

【希尔排序算法】详解：原理、实现与优化

【希尔排序算法】详解：原理、实现与优化

【希尔排序算法】详解：原理、实现与优化 * 一、算法概述 * 基本特性 * 二、算法原理详解 * 核心思想 * 增量序列选择 * 三、算法流程图示 * 示例数组：[8, 9, 1, 7, 2, 3, 5, 4, 6, 0] * 初始状态 * 第一轮：gap=5 * 第二轮：gap=2 * 第三轮：gap=1（标准插入排序） * 四、完整Java实现 * 五、算法分析 * 时间复杂度分析 * 空间复杂度 * 稳定性 * 六、实际应用场景 * 七、与其他排序算法的对比 * 八、总结 🌺The Begin�

By Ne0inhk

傅里叶变换 | FFT 与 DFT 原理及算法

注：本文为 “傅里叶变换 | FFT 与 DFT” 相关合辑。 英文引文，机翻未校。 中文引文，略作重排。 图片清晰度受引文原图所限。 如有内容异常，请看原文。 Fast Fourier Transform (FFT) 快速傅里叶变换（FFT） In this section we present several methods for computing the DFT efficiently. In view of the importance of the DFT in various digital signal processing applications, such as linear filtering,

By Ne0inhk
链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧

✨链表进阶核心 | LeetCode 92 区间反转：吃透递归反转与哨兵技巧🎯 * 视频地址 * 🚀 开篇引论：链表反转的进阶之路 * 🔄 基础筑基：链表【前n个节点】递归反转 * 1. 函数定义与核心功能 * 2. 递归实现思路拆解 * 3. 直观调用示例 * 4. 关键代码实现（C++）与详解 * 🎯 实战攻坚：LeetCode 92 链表区间反转 * 1. 题目问题描述 * 2. 神器加持：虚拟头节点（哨兵）技巧 * 3. 整体解题思路 * 4. 完整代码实现（C++）与逐行解析 * 5. 算法复杂度分析 * 📚 算法原理深度剖析 * 1. 递归反转的核心原理 * 2. 虚拟头节点的底层逻辑 * 💡 算法学习核心建议 * 结语 * ✅ 关键点回顾 视频地址

By Ne0inhk
贪心算法（局部最优实现全局最优）第一篇

贪心算法（局部最优实现全局最优）第一篇

目录 1. 什么是贪心算法 2. 贪心算法的解题步骤 3. 具体例题及代码 3.1 LeetCode860. 柠檬水找零 3.2 LeetCode2208. 将数组和减半的最少操作次数 3.3 LeetCode179. 最大数 从这篇文章开始，我们开始讲解贪心算法。 1. 什么是贪心算法 贪心算法是算法设计中的经典思想，核心逻辑用一句话就能概括 ——每一步都做出当前情况下的最优选择，不回头、不纠结，最终期望得到全局最优解。它不像动态规划那样依赖中间状态存储，也不用回溯尝试所有可能，凭借 “直来直往” 的思路，成为解决特定问题的高效方案。 2. 贪心算法的解题步骤 1. 问题拆解：将复杂问题拆分成多个连续的局部决策步骤。 2. 确定贪心策略：明确每一步的 “最优标准”（比如 “选最小”“选最大”“选最早结束”）。 3. 验证可行性：

By Ne0inhk