【动态规划】子序列问题（一）-海口c网

【动态规划】子序列问题（一）

article/2025/8/11 19:25:44

📝前言说明：

本专栏主要记录本人的动态规划算法学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题
简单多状态（一）	简单多状态（二）
子数组系列（一）	子数组系列（二）
子序列问题（一）	子序列问题（二）
回文串问题	两个数组dp问题（一）
两个数组的dp问题（二）	01背包问题
完全背包	二维的背包问题
其他

题目

什么是子序列
300. 最长递增子序列
- 优质解
376. 摆动序列
- 个人解
673. 最长递增子序列的个数
- 优质解
646. 最长数对链
- 个人解

什么是子序列

子序列：数组中不连续的⼀段，即：每个位置的数字都有选 / 不选两种情况

300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
在这里插入图片描述

优质解

思路：

dp[i]：以i位置为结尾的所有子序列中的最长严格递增子序列
状态转移：构成以i位置为结尾的子序列有两种情况
- 子序列长度为 1 ：单独i位置成一个子序列
- 子序列长度大于1：依据i紧跟的前一个元素可以分为i种情况（但实际上子序列的数量远远大于 i，只不过我们描述到这种程度已经可以解题了）
  - ... nums[i - 1], nums[i]
  - ... nums[i - 2],nums[i]
  - …
  - nums[0], nums[i]
状态转移方程
- 长度为 1：dp[i] = 1;
- 长度大于1：我们设计紧跟nums[i]的元素的下标为j（在一次循环里：i - 1 >= j >=0）：
  - if(nums[j] < nums[i]) dp[i] = dp[j] + 1
  - j遍历一遍，找到最大值max_dp，dp[i] = max_dp
初始化：每个元素对应dp的最小值：1
填表顺序：从左往右
返回值：dp表中的最大值

代码：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);for(int i = 1; i < n; i++){int dp_max = 1;for(int j = i - 1; j >= 0; j--)if(nums[j] < nums[i])dp_max = max(dp_max, dp[j] + 1);dp[i] = dp_max;}int ans = 1;for(auto x:dp)ans = max(ans, x);return ans;}
};

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

376. 摆动序列

题目链接：https://leetcode.cn/problems/wiggle-subsequence/description/
在这里插入图片描述

个人解

思路：

和上一题一样
一个 2 * n 的 dp数组（第 i 个位置有两种状态 > 或 <）
dp[0][i] ：记录第 i 个位置为<时，以i位置为结尾的最长摆动数组

用时：12:00
屎山代码：

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();vector<vector<int>> dp(2, vector(n, 1)); int ans = 1;for(int i = 1; i < n; i++){for(int j = i - 1; j >= 0; j--){if(nums[i] > nums[j])dp[1][i] = max(dp[1][i], dp[0][j] + 1);else if(nums[i] < nums[j])dp[0][i] = max(dp[0][i], dp[1][j] + 1);}ans = max(max(dp[0][i], dp[1][i]), ans);}return ans;}
};

时间复杂度： $O(n^2)$ ，用贪心策略可以把时间降到 $O (n)$
空间复杂度： $O (n)$

673. 最长递增子序列的个数

题目链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
在这里插入图片描述

优质解

思路：

dp[i]: 以 i 位置结尾的最递增子序列
cnt[i]: 以该位置结尾的最长递增子序列的个数

代码：

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);vector<int> cnt(n, 1);int maxlen = 1, ans = 1;for(int i = 1; i < n; i++){for(int j = i - 1; j >= 0; j--){// 获得以 i 位置结尾的最长子序列和 最长子序列的个数if(nums[i] > nums[j]){if(dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;cnt[i] = cnt[j]; // i 的前面为 j 但是，这代表的子串可不只一个}else if(dp[i] == dp[j] + 1){cnt[i] += cnt[j];}}}// 更新 ansif(dp[i] > maxlen){ans = cnt[i];maxlen = dp[i];}else if(dp[i] == maxlen)ans += cnt[i];}return ans;}
};

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

646. 最长数对链

题目链接：https://leetcode.cn/problems/maximum-length-of-pair-chain/description/
在这里插入图片描述

个人解

思路：

按第一个元素的大小排一下序
因为后面pair的第二个元素要大于前面pair的第一个元素，所以后pair的第一个元素肯定也要大于前pair的第一个元素

用时：5:00
屎山代码：

class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {int n = pairs.size();sort(pairs.begin(), pairs.end());vector<int> dp(n, 1);int ans = 1;for(int i = 0; i < n; i++){for(int j = i - 1; j >= 0; j--){if(pairs[i][0] > pairs[j][1])dp[i] = max(dp[i], dp[j] + 1);}ans = max(ans, dp[i]);}return ans;}
};