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

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

Qwen-Image-Lightning：重新定义AIGC效率的极速图像生成技术

Qwen-Image-Lightning：重新定义AIGC效率的极速图像生成技术 【免费下载链接】Qwen-Image-Lightning 项目地址: https://ai.gitcode.com/hf_mirrors/lightx2v/Qwen-Image-Lightning 技术突破：从100步到8步的效率革命 在AIGC技术快速迭代的今天，动态蒸馏机制正成为突破生成效率瓶颈的关键技术。Qwen-Image-Lightning通过创新性的FlowMatchEulerDiscreteScheduler调度器，构建了一套类似"扩散模型加速器"的技术架构。该机制采用动态时间偏移算法，能够智能识别图像生成过程中的关键阶段，在保持85%以上图像质量的同时，将传统扩散模型需要的100步推理压缩至仅需8步即可完成。 这项技术突破的核心价值在于解决了AIGC领域长期存在的"质量-效率"悖论。通过对模型各层特征提取能力的精准评估，动态蒸馏机制能够在生成过程中动态调整计算资源分配，将算力集中在对图像质量起关键作用的阶段。某互联网内容平台的实测数据显示，采用该技术后，其UGC内容生成效率提升了

By Ne0inhk

PyCharm+GitHub Copilot零成本配置手册：学生认证/2FA/汉化疑难一次解决

PyCharm + GitHub Copilot 零成本配置手册：从学生认证到流畅编码的全链路实战 作为一名学生开发者，你是否曾羡慕那些能流畅使用AI编程助手的同行，却苦于复杂的认证流程、网络环境的掣肘，或是面对英文界面时的些许不适？将前沿的AI工具无缝融入日常开发工作流，本应是一个提升效率的愉悦过程，而非充满障碍的挑战。今天，我们就来彻底解决这些问题，打造一套专为学生群体设计、开箱即用的PyCharm与GitHub Copilot生产力解决方案。这套方案不仅会手把手带你完成从学生身份验证到IDE集成的每一步，更会聚焦于国内用户常见的“水土不服”问题，提供稳定的替代方案和优化技巧，让你真正零成本、零门槛地拥抱AI辅助编程。 1. 基石构建：GitHub学生认证与账户安全加固 在享受任何福利之前，一个经过验证且安全的GitHub账户是首要前提。学生认证是获取GitHub Copilot Pro免费使用权的钥匙，而双重身份验证（2FA）则是守护这把钥匙的保险箱。 1.1 高效通过GitHub学生认证 学生认证的核心在于向GitHub证明你当前的在读身份。整个过程需要细心，但绝非

By Ne0inhk

四大推理框架实战指南：SGLang、Ollama、vLLM与LLaMA.cpp的性能调优与场景适配

1. 四大推理框架，到底该怎么选？ 最近和几个做AI应用的朋友聊天，发现大家选推理框架时都挺纠结的。有人想在公司服务器上搞个高并发的问答服务，有人只想在自己电脑上跑个模型玩玩，还有人想把模型塞进树莓派里做点小玩意儿。需求五花八门，但面对SGLang、Ollama、vLLM、LLaMA.cpp这几个名字，往往就懵了，不知道哪个才是自己的“真命天子”。 其实，选框架这事儿，就跟选车一样。你不能光看谁跑得快（性能），还得看它烧什么油（硬件需求），好不好开（易用性），以及能不能开进你家车库（部署环境）。vLLM就像一辆高性能跑车，在高速服务器公路上能飙出极限速度，但你得给它配顶级加油站（A100/H100 GPU）和专用赛道（Linux系统）。而LLaMA.cpp更像一辆全地形越野车，不挑路，甚至没路（纯CPU）也能跑，虽然速度慢点，但胜在哪儿都能去。 我自己折腾这些框架也有一段时间了，从最开始在个人笔记本上装Ollama尝鲜，到后来在公司用vLLM搭建对外服务，再到为了一个边缘计算项目死磕LLaMA.cpp的编译优化，可以说每个坑都踩过。

By Ne0inhk

AudioSeal Pixel Studio实战教程：结合Whisper语音识别实现‘水印+ASR’双验证

AudioSeal Pixel Studio实战教程：结合Whisper语音识别实现'水印+ASR'双验证 1. 工具介绍与核心价值 AudioSeal Pixel Studio是一款基于Meta开源的AudioSeal算法构建的专业音频保护工具。它能够在保持原始音质几乎不变的情况下，为音频文件嵌入隐形数字水印，同时具备强大的抗干扰能力。这款工具特别适合用于识别AI生成音频、保护音频版权等场景。 工具采用Streamlit框架开发，界面设计采用"海蓝色像素"风格，为用户提供清爽专业的操作体验。通过本教程，您将学会如何结合Whisper语音识别技术，实现音频水印与语音内容双重验证的工作流程。 2. 环境准备与快速部署 2.1 系统要求 * Python 3.8或更高版本 * NVIDIA GPU（推荐）或性能良好的CPU * 至少4GB可用内存 2.2 安装步骤 使用pip一键安装所需依赖： pip install audioseal streamlit

By Ne0inhk