前言
最近刷了子序列系列的题型，一共八个力扣题，这里对子序列问题进行一个简单的总结，全是动态规划的解法，当然里边有些题选有更优的解法。
1. 动态规划解题思路
动态规划（Dynamic Programming, DP）是一种在计算机科学和数学中用于解决最优化问题的方法。它特别适用于可以分解为互相重叠的子问题的问题，并且这些子问题的解可以被存储起来以避免重复计算，从而提高效率。
首先，我们要熟悉动态规划的套路也要理解为什么要用动态规划，什么题型可以用动态规划来解决。
动态规划的基本思想
- 最优子结构：问题的最优解包含了其子问题的最优解。
- 重叠子问题：求解过程中，子问题被重复计算多次。
以下是动态规划解题思路：
写代码一共是四个块：建表，初始化，填表，返回值。
但是解题思考六个步骤：分析题意，状态表示建表，找状态转移方程，初始化，填表顺序，返回值。
1. 建表：
- 怎么建表，这根据我们的经验和题意来写，一般是以 i 为结尾，也可以是开始，满足题目条件要求的结果。dp【i】。
- 但是有的时候一个表不能解决问题，可能有另外的情况，满足这个或者满足哪个等多个条件，要建多个表，f【i】，g【i】。
- 也有的时候，一维表无法满足要求，因为需要可能是，满足这个并满足哪个等多条件，需要建多维表 dp【i】【j】，一般二维就够了。
- 也有的时候，一维表无法满足要求，因为需要可能是，满足这个并满足哪个等多条件，见多个表f【i】，g【i】，因为g【i】状态转移方程依靠f【i】才能推出来，
2. 找状态转移方程：
- 这里边可以分情况，看建表怎么样，有时候建的表无法找出状态转移方程，那么就需要你重新再根据条件重新建表
- 如果是 dp【i】，那么找dp【i-1】或者 再带个 dp【i-2】的关系推方程。
- 如果是 f【i】，g【i】，第一种，那么根据情况选择更新的 f【i】还是 g【i】，注意这个f【i】/ g【i】更新的时候找df【i-1】或者dg【i-1】的关系。
- 如果是 dp【i】【j】，那么也根据条件找，看看i 和 j 能不能推出什么往前推，都是根据条件。
3. 初始化：
- 一般都是初始化前几个，根据状态转化方程或者根据建表dp【i】含义来推导。
- 有时候为了初始化的遍历，在建表的时候空间多写一个，或者多建一圈什么的。
4. 填表顺序：
- 填表顺序也是根据状态转换方程来推导，一般从上到下，从左到右，或者从右到左，上下左右随意组合。
- 根据状态转换方程推，主要是看dp【i】是依赖dp【i-1】还是依赖dp【i+1】，依赖前
边的从左到右，依赖后边的从右边到左边。
5. 返回值：
- 返回值根据题目要求来写，基本上要么返回最后一个值，要么返回最值，或者返回和。
2. 八个子序列问题实战解析
2.1 最长递增子序列
class Solution {
int n ;
public int lengthOfLIS(int[] nums) {
int ret =0;
n=nums.length;
//动态规划
int[] dp = new int[n];
//初始化,本身是一个,所以至少有一个
Arrays.fill(dp,1);
//填表时 dp[i] 的值要依赖 dp[i+1] 的值,所以是从后往前填表
for(int i = n-1;i>=0;i--){
//对 i 起点位置往后遍历,找最大的一个值
for(int j = i+1;j<n;j++){
if(nums[i]<nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
ret = Math.max(ret,dp[i]);
}
//dfs表示以当前位置为起点最长的递增子序列
// int[] memo = new int[n];
// for(int i =0;i<n;i++){
// ret = Math.max(ret,dfs(i,nums,memo));
// }
return ret;
}
//1:纯递归超时
//2:记忆化搜索 78ms
//3:动态规划 64ms 2和3的时间复杂度是相同的
public int dfs(int pos,int[] nums,int[] memo){
//对当前位置的后面的每一个位置都判断,如果大于返回值就等于那个位置为起点的最大长度+1
//如果是最后一个数,那么就不会进去,但至少也又一个
if(memo[pos] != 0){
return memo[pos];
}
int ret= 1;
for(int i = pos+1;i<n;i++){
if(nums[i]>nums[pos]){
ret = Math.max(ret,dfs(i,nums,memo)+1);
}
}
memo[pos] = ret;
return ret;
}
}题目：给你一个整数数组
nums，找到其中最长严格递增子序列的长度。
- 状态表示：以 i 位置为结尾的最长严格递增子序列的长度
- 状态转移方程：从 i 的左边找，当找的元素nums【j】小于 nums【i】,dp【i】 = Math.max(dp【j】+ 1，dp【i】），因为要找很多 j ，把左边的全部找完，所有取最大值
- 初始化：长度至少为1，所以直接所有都初始化为1
- 填表顺序：依赖 j 在 i 左边，那么从左到右，i 往右走，j 往 i 的左边遍历过去
- 返回值：返回最大值，加个变量更新最大
2.2 摆动序列
class Solution {
public int wiggleMaxLength(int[] nums) {
//以 i 位置为结尾的最长子序列且是摆动序列的长度
//这里结尾分上升趋势和下降趋势
int n = nums.length;
if(n < 2) return n;
int[] f = new int[n]; //上升
int[] g = new int[n]; //下降
//初始化
Arrays.fill(f, 1);
Arrays.fill(g, 1);
int ret = 1;
for(int i = 1; i < n; i++){
for(int j = i - 1; j >= 0; j--){
if(nums[j] < nums[i]){
//如果上升趋势
f[i] = Math.max(f[i], g[j] + 1);
}else if(nums[j] > nums[i]){
g[i] = Math.max(g[i], f[j] + 1);
}
}
ret = Math.max(ret, Math.max(f[i], g[i]));
}
return ret;
}
}
题目：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。给你一个整数数组
nums，返回nums中作为 摆动序列 的 最长子序列的长度 。
- 状态表示：这里是摆动序列，初步判断直接以 i 为结尾的作为摆动序列的最长子序列的长度，dp【i】，但是推到状态转移方程的时候发现有两种情况，分别是以 i 为结尾上升和下降，所以这里要有两个，f【i】（上升），g【i】下降
- 状态转移方程：从 i 的左边找，当找的元素nums【j】小于 nums【i】,那么就是上升，则f【i】 = Math.max（g【j】+ 1，f【i】）因为要找很多 j ，把左边的全部找完，所有取最大值。同理g【i】 = Math.max（f【j】+ 1，g【i】）
- 初始化：长度至少为1，所以直接所有都初始化为1
- 填表顺序：依赖 j 在 i 左边，那么从左到右填表，i 往右走，j 往 i 的左边遍历过去
- 返回值：返回最大值，加个变量更新最大
2.3 最长递增子序列的个数
673. 最长递增子序列的个数 - 力扣（LeetCode）
class Solution {
public int findNumberOfLIS(int[] nums) {
//相当于https://leetcode.cn/problems/longest-increasing-subsequence/的进阶版
//这里设两个dp表
int n = nums.length;
int[] len = new int[n]; //以i位置为结尾的最长递增子序列的长度
int[] count = new int[n];//以i位置为结尾最长递增子序列的个数
//初始化
for(int i = 0; i < n; i++) len[i] = count[i] = 1;
//从左往右填表
for(int i = 1; i < n; i++){
for(int j = i - 1; j >= 0; 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];
}//如果找到小的值就不理会
}
}
}
//现在i位置为结尾的最长递增子序列长度和个数都已完成更新
//返回值
int maxLen = len[0], retCount = count[0];
for(int i = 1; i < n; i++){
if(len[i] == maxLen){
retCount += count[i];
}else if(len[i] > maxLen){
maxLen = len[i];
retCount = count[i];
}
}
return retCount;
}
} 
题目：
给定一个未排序的整数数组
nums， 返回最长递增子序列的个数 。注意 这个数列必须是 严格 递增的。
状态表示：先尝试定义⼀个状态：以 i 为结尾的最⻓递增⼦序列的「个数」。那么问题就来了，我都不知道 以 i 为结尾的最⻓递增⼦序列的「⻓度」是多少，我怎么知道最⻓递增⼦序列的个数呢？ 因此，我们解决这个问题需要两个状态，⼀个是「⻓度」，⼀个是「个数」： len[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的⻓度； count[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的个数。
状态转移方程：
- 当遍历到元素
nums[i]时，需要检查其左边所有元素nums[j]（其中j < i）- 若
nums[j] < nums[i]，说明可以将nums[i]接在以j结尾的递增子序列后- 若
len[j] + 1 > len[i]，则更新len[i] = len[j] + 1，并将count[i]重置为count[j]（因为找到了更长的子序列）- 若
len[j] + 1 == len[i]，则count[i] += count[j]（因为找到了相同长度的新子序列）初始化：每个元素自身可作为长度为 1 的递增子序列
填表顺序：
依赖 j 在 i 左边，那么从左到右填表，i 往右走，j 往 i 的左边遍历过去
- 从左到右依次处理每个元素（外层循环
i从 1 到 n-1）- 对于每个
i，从其左边最近的元素开始向前遍历（内层循环j从 i-1 到 0）- 这种顺序确保在计算
len[i]和count[i]时，所有可能的len[j]和count[j]已计算完成返回值：根据上边的小demo得来
2.4 最长数对链
646. 最长数对链 - 力扣（LeetCode）
class Solution {
public int findLongestChain(int[][] pairs) {
//由于数组里的数对列是随机的,所以需要排序
//排序完之后保证填表顺序,而且排序之后就与最长递增子序列一样了
//最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/
int n = pairs.length;
// Arrays.sort(pairs, Comparator.comparingInt(a -> a[0]));
Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
题目概述
给定一个二维整数数组
pairs，其中每个元素为[a, b]，若存在数对序列(i1,j1), (i2,j2), ..., (in,jn)满足j1 < i2, j2 < i3, ..., jn-1 < in，则称该序列为数对链。要求找出可以形成的最长数对链的长度。核心思路
该问题本质上是最长递增子序列 (LIS) 的变种，区别在于：
- 传统 LIS 要求后一个元素值大于前一个元素值
- 数对链要求后一个数对的首个元素大于前一个数对的第二个元素
状态表示
- 定义一维数组
dp，其中dp[i]表示以第i个数对结尾的最长数对链长度状态转移方程
- 首先将数对按首个元素升序排序，确保处理顺序的合理性
- 对于每个数对
pairs[i]，遍历其之前所有数对pairs[j]（j < i）- 若
pairs[i][0] > pairs[j][1]，说明可以将pairs[i]接在pairs[j]之后形成更长链- 状态转移表达式：
其中dp[i] = max(dp[i], dp[j] + 1)j满足pairs[i][0] > pairs[j][1]初始化
- 每个数对自身可作为长度为 1 的链，因此：
Arrays.fill(dp, 1);填表顺序
- 从左到右依次处理每个数对（外层循环
i从 1 到 n-1）- 对于每个数对
i，遍历其之前所有数对j（内层循环j从 0 到 i-1）- 这种顺序确保在计算
dp[i]时，所有可能的dp[j]已计算完成返回值计算
- 在遍历过程中维护最大值
res，记录当前找到的最长链长度- 具体实现：
int res = 1; for (int i = 1; i < n; ++i) { // 更新dp[i]... res = Math.max(res, dp[i]); } return res;
2.5 最长定查子序列
class Solution {
public int longestSubsequence(int[] arr, int difference) {
//这道题可以直接常规动态规划来做
//但是这里有两个优化的点
//1：用哈希表记录，到后边就不用每次去遍历找数来对比了
//2：直接用哈希表来写动态规划
int n = arr.length;
HashMap<Integer, Integer> hash = new HashMap<>();
//初始化
int ret = 1;
for(int i = 0; i < n; i++){
int a = arr[i], b = a - difference;
int newValue = hash.getOrDefault(b, 0) + 1;
hash.put(a, newValue);
ret = Math.max(ret, newValue);
}
return ret;
}
}题目概述
给定一个整数数组
arr和一个整数difference，找出并返回arr中最长等差子序列的长度，该子序列中相邻元素之间的差等于difference。子序列不需要连续，但必须保持元素的相对顺序。核心思路
本题可使用动态规划结合哈希表进行优化，核心思想如下：
动态规划状态：定义
dp[x]表示以元素x结尾的最长等差子序列的长度状态转移：对于每个元素
arr[i]，检查arr[i] - difference是否存在于之前的状态中。若存在，则dp[arr[i]] = dp[arr[i] - difference] + 1；否则，dp[arr[i]] = 1哈希表优化：使用哈希表而非数组存储状态，可高效处理大范围整数并快速查找历史状态
状态表示
哈希表
hash：键为元素值，值为以该元素结尾的最长等差子序列的长度状态转移方程
对于每个元素
arr[i]，设当前元素为a，其前一个元素为b = a - difference，则状态转移方程为：hash[a] = hash.getOrDefault(b, 0) + 1
hash.getOrDefault(b, 0)获取以b结尾的最长子序列长度（若不存在则为 0）
+1表示将当前元素a加入子序列后的新长度初始化
哈希表初始为空
结果变量
ret初始化为 1（至少存在一个元素构成的子序列）填表顺序
从左到右遍历数组
arr，依次处理每个元素对于每个元素
arr[i]，立即更新哈希表和结果变量返回值计算
在遍历过程中维护全局最大值
ret，记录当前找到的最长子序列长度最终返回
ret算法复杂度分析
时间复杂度：O (n)，只需遍历数组一次
空间复杂度：O (n)，主要用于哈希表存储状态
2.6 最长的斐波那契子序列的长度
873. 最长的斐波那契子序列的长度 - 力扣（LeetCode）1027. 最长等差数列 - 力扣（LeetCode）
class Solution {
public int lenLongestFibSubseq(int[] arr) {
//斐波那契是前两个数确定第三个数
//所以这里需要先确定两个数，这里用二维dp
int n = arr.length;
//以i，j位置为结尾的斐波那契子序列中最长的长度
int[][] dp = new int[n][n];
//初始化，因为是i ， j所以至少长度为2
for(int[] i : dp){
Arrays.fill(i, 2);
}
//这里用hash缓存下标和数据，不然得遍历找某个数
HashMap<Integer, Integer> map = new HashMap<>();
int ret = 2;
//填表
for(int j = 0; j < n; j++){
for(int i = j-1; i > 0; i--){
int b = arr[i], c = arr[j], a = c - b;
if(map.containsKey(a) && a < b){ //这里严格递增省事了
int k = map.get(a);
dp[i][j] = dp[k][i] + 1;
ret = Math.max(ret, dp[i][j]);
}
}
map.put(arr[j], j);
}
return ret == 2 ? 0 : ret;
}
}题目概述
给定一个严格递增的整数数组
arr，找出其中最长的斐波那契子序列的长度。斐波那契子序列满足：对于序列中任意位置k ≥ 2，都有arr[k] = arr[k-1] + arr[k-2]。子序列不需要连续，但必须保持元素的相对顺序。若不存在长度≥3 的斐波那契子序列，返回 0。核心思路
斐波那契序列特性：每个元素由前两个元素唯一确定，即若存在
a + b = c，则a, b, c可构成斐波那契三元组动态规划状态定义：使用二维数组记录以任意两个元素结尾的子序列长度
哈希表优化：快速查找元素对应的索引，避免暴力遍历
状态表示
定义二维数组
dp[i][j]，表示以索引i和j处的元素作为最后两个元素的最长斐波那契子序列的长度
其中
i < j，即arr[i]是子序列的倒数第二个元素，arr[j]是最后一个元素
dp[i][j]的值表示该子序列的长度状态转移方程
对于每个元素对
(i, j)（i < j），计算前一个元素a = arr[j] - arr[i]若
a存在于数组中且a < arr[i]（保证递增顺序），找到其索引k- 状态转移逻辑：
dp[i][j] = dp[k][i] + 1含义：若存在以
(k, i)结尾的斐波那契子序列，则可在其末尾添加arr[j]形成更长序列初始化
- 每个元素对
(i, j)本身至少构成长度为 2 的子序列，因此：for (int[] row : dp) { Arrays.fill(row, 2); }填表顺序
外层循环遍历
j从 0 到 n-1（当前最后一个元素的索引）内层循环遍历
i从j-1到 1（保证i < j且i至少为 1，确保存在前一个元素）在处理完
j的所有i后，将arr[j]存入哈希表，以便后续查找
这样保证在处理更大的
j时，前面的元素已被记录返回值计算
遍历过程中维护全局最大值
ret，记录最长子序列长度若
ret始终为 2，说明不存在长度≥3 的斐波那契子序列，返回 0否则返回
ret算法复杂度分析
时间复杂度：O(n²)
两层嵌套循环遍历所有元素对
(i, j)哈希表查找操作复杂度为 O (1)
空间复杂度：O(n)
哈希表存储元素值到索引的映射，空间为 O (n)
二维 dp 数组空间为 O (n²)
2.7 等查数列划分
class Solution {
public int longestArithSeqLength(int[] nums) {
//这道题跟上道题https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/特别相似，就是填表的时候有个坑要注意了
//由于最长等差子序列，无法找到i位置和i-1位置的关系
//但是i 和 i-1 能确定 i-2甚至整个等差子序列的长度，
//那么dp表就记录以 i 和 i-1的为下标的两个结尾数的最长等差子序列的长度
int n = nums.length;
int[][] dp = new int[n][n];
//只初始右上边，只用得到那些
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
dp[i][j] = 2;
}
}
// a b c，b c 找 a
//这里用Hash表优化每次找a
// 元素 下标
HashMap<Integer,Integer> hash = new HashMap<>();
//这里填表直接从第三个开始填,记得把前两个Hash初始化
hash.put(nums[0], 0);
int ret = 2;
//为了每次存最靠近 b 的那个数，就先固定b，然后移动c往后遍历固定找b前面的a
for(int i = 1; i < n; i++){
for(int j = i + 1; j < n; j++){
int b = nums[i], c = nums[j], a = 2 * b - c;
if(hash.containsKey(a)){
int k = hash.get(a);
dp[i][j] = dp[k][i] + 1;
//更新最大值
ret = Math.max(dp[i][j], ret);
}
}
//更新Hash表
hash.put(nums[i], i);
}
return ret;
}
}题目概述
给定一个整数数组
nums，找出其中最长等差数列的长度。等差数列是指一个序列中任意相邻元素之间的差相等。子序列不需要连续，但必须保持元素的相对顺序。核心思路
本题与最长斐波那契子序列问题类似，但等差数列的定义更为宽泛。关键在于利用二维动态规划记录以任意两个元素结尾的等差数列长度，并通过哈希表快速定位前一个可能的元素。
状态表示
定义二维数组
dp[i][j]，表示以索引i和j处的元素作为最后两个元素的最长等差数列的长度其中
i < j，即dp[i][j]表示以nums[i]和nums[j]为末尾的等差数列的最大长度状态转移方程
- 对于每个元素对
(i, j)（i < j），计算前一个元素a：a = 2 * nums[i] - nums[j]该公式基于等差数列的性质：若
a, b, c成等差数列，则2b = a + c，即a = 2b - c- 若
a存在于数组中（通过哈希表快速查找），则：dp[i][j] = dp[k][i] + 1其中
k是a的索引，表示在以(k, i)结尾的等差数列后添加nums[j]初始化
- 每个元素对
(i, j)本身至少构成长度为 2 的等差数列，因此：for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { dp[i][j] = 2; } }填表顺序
外层循环遍历
i从 1 到 n-1（当前倒数第二个元素的索引）内层循环遍历
j从i+1到 n-1（当前最后一个元素的索引）对于每个
(i, j)对，检查是否存在满足条件的a，并更新状态在处理完当前
i的所有j后，将nums[i]存入哈希表，确保哈希表中始终保存元素的最新（最右侧）位置返回值计算
在遍历过程中维护全局最大值
ret，记录最长等差数列的长度最终返回
ret算法复杂度分析
时间复杂度：O(n²)
两层嵌套循环遍历所有元素对
(i, j)哈希表操作时间复杂度为 O (1)
空间复杂度：O(n²)
主要用于存储二维 dp 数组
2.8 等查数列划分Ⅱ
446. 等差数列划分 II - 子序列 - 力扣（LeetCode）
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
//这道题怎么说呢，求数目和，那么就不能和之前求长度一样只挑选一个了
//同样，一个下标确定不了等差数列，那么需要两个下标。
//以i，j为结尾的等差子序列的数目
int n = nums.length;
int[][] dp = new int[n][n];
//这里需要hash表来记录下标和数来对找 等差数列 a b c 中的a时优化
// 元素 下标数组 这里有个用例会比较恶心，超int溢出会默认最大最小，所有用long
Map<Long,List<Integer>> hash = new HashMap<>();
for(int i = 0; i < n; i++){
long tmp = (long)nums[i];
if(!hash.containsKey(tmp))
hash.put(tmp, new ArrayList<Integer>());
hash.get(tmp).add(i);
}
int ret = 0;
//初始化，对于dp来说，如果只有两个，找不到等差那么就为0，所以这里默认所有为0
//填表
for(int j = 2; j < n; j++){
for(int i = 1; i < j; i++){
long a = 2L * nums[i] - nums[j];
if(hash.containsKey(a)){
for(int k : hash.get(a)){
if(k < i) dp[i][j] += dp[k][i] + 1;
else break;
}
}
ret += dp[i][j];
}
}
return ret;
}
}题目概述
给定一个整数数组
nums，返回该数组中所有等差数列的数目。等差数列是指至少包含三个元素，且任意相邻元素之间的差相等的子序列。子序列不需要连续，但必须保持元素的相对顺序。核心思路
本题需要统计所有可能的等差数列数目，与之前求最长等差数列长度的问题相比，需要计算所有符合条件的子序列数目。使用二维动态规划结合哈希表优化查找效率。
状态表示
定义二维数组
dp[i][j]，表示以索引i和j处的元素作为最后两个元素的等差数列的数目其中
i < j，即dp[i][j]表示以nums[i]和nums[j]为末尾的等差数列的数量状态转移方程
对于每个元素对
(i, j)（i < j），计算前一个元素a：a = 2 * nums[i] - nums[j]该公式基于等差数列的性质：若
a, b, c成等差数列，则2b = a + c若
a存在于数组中（通过哈希表查找），遍历所有a的索引k（满足k < i）：dp[i][j] += dp[k][i] + 1其中
dp[k][i]表示以(k, i)结尾的等差数列数目，+1表示新增的三元组(k, i, j)初始化
所有
dp[i][j]初始化为 0，表示没有找到等差数列填表顺序
外层循环遍历
j从 2 到 n-1（确保至少有三个元素）内层循环遍历
i从 1 到 j-1（确保i < j）对于每个
(i, j)对，计算a = 2 * nums[i] - nums[j]，并检查哈希表中是否存在a若存在，遍历所有
a的索引k（按升序排列），当k < i时更新dp[i][j]将
dp[i][j]的值累加到结果ret中返回值计算
在遍历过程中累加所有
dp[i][j]的值，最终返回ret算法复杂度分析
时间复杂度：O(n²)
两层嵌套循环遍历所有元素对
(i, j)哈希表操作时间复杂度为 O (1)，但最坏情况下可能遍历所有
a的索引空间复杂度：O(n²)
主要用于存储二维 dp 数组和哈希表