【动态规划】一次性整理子序列问题题型系列，八个例题实战详细解析 （包含我自己精心整理的动态规划解题思路）_子序列问题常见套路

 

题目概述

给定一个二维整数数组 pairs，其中每个元素为 [a, b]，若存在数对序列 (i1,j1), (i2,j2), ..., (in,jn) 满足 j1 < i2, j2 < i3, ..., jn-1 < in，则称该序列为数对链。要求找出可以形成的最长数对链的长度。

核心思路

该问题本质上是最长递增子序列 (LIS) 的变种，区别在于：

• 传统 LIS 要求后一个元素值大于前一个元素值
• 数对链要求后一个数对的首个元素大于前一个数对的第二个元素

状态表示

• 定义一维数组 dp，其中 dp[i] 表示以第 i 个数对结尾的最长数对链长度

状态转移方程

1. 首先将数对按首个元素升序排序，确保处理顺序的合理性
2. 对于每个数对 pairs[i]，遍历其之前所有数对 pairs[j]（j < i）
3. 若 pairs[i][0] > pairs[j][1]，说明可以将 pairs[i] 接在 pairs[j] 之后形成更长链
4. 状态转移表达式：

   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 最长定查子序列

1218. 最长定差子序列 - 力扣（LeetCode）

class Solution { public int longestSubsequence(int[] arr, int difference) { //这道题可以直接常规动态规划来做 //但是这里有两个优化的点 //1：用哈希表记录，到后边就不用每次去遍历找数来对比了 //2：直接用哈希表来写动态规划 int n = arr.length; HashMap 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 map = new HashMap(); int ret = 2; //填表 for(int j = 0; j  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。

核心思路

1. 斐波那契序列特性：每个元素由前两个元素唯一确定，即若存在 a + b = c，则 a, b, c 可构成斐波那契三元组

2. 动态规划状态定义：使用二维数组记录以任意两个元素结尾的子序列长度

3. 哈希表优化：快速查找元素对应的索引，避免暴力遍历

状态表示

• 定义二维数组 dp[i][j]，表示以索引 i 和 j 处的元素作为最后两个元素的最长斐波那契子序列的长度

  • 其中 i < j，即 arr[i] 是子序列的倒数第二个元素，arr[j] 是最后一个元素

  • dp[i][j] 的值表示该子序列的长度

状态转移方程

1. 对于每个元素对 (i, j)（i < j），计算前一个元素 a = arr[j] - arr[i]

2. 若 a 存在于数组中且 a < arr[i]（保证递增顺序），找到其索引 k

3. 状态转移逻辑：

   dp[i][j] = dp[k][i] + 1

   含义：若存在以 (k, i) 结尾的斐波那契子序列，则可在其末尾添加 arr[j] 形成更长序列

初始化

• 每个元素对 (i, j) 本身至少构成长度为 2 的子序列，因此：

  for (int[] row : dp) { Arrays.fill(row, 2);}

填表顺序

1. 外层循环遍历 j 从 0 到 n-1（当前最后一个元素的索引）

2. 内层循环遍历 i 从 j-1 到 1（保证 i < j 且 i 至少为 1，确保存在前一个元素）

3. 在处理完 j 的所有 i 后，将 arr[j] 存入哈希表，以便后续查找

   • 这样保证在处理更大的 j 时，前面的元素已被记录

返回值计算

1. 遍历过程中维护全局最大值 ret，记录最长子序列长度

2. 若 ret 始终为 2，说明不存在长度≥3 的斐波那契子序列，返回 0

3. 否则返回 ret

算法复杂度分析

• 时间复杂度：O(n²)

  • 两层嵌套循环遍历所有元素对 (i, j)

  • 哈希表查找操作复杂度为 O (1)

• 空间复杂度：O(n)

  • 哈希表存储元素值到索引的映射，空间为 O (n)

  • 二维 dp 数组空间为 O (n²)

2.7 等查数列划分

1027. 最长等差数列 - 力扣（LeetCode）

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 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] 为末尾的等差数列的最大长度

状态转移方程

1. 对于每个元素对 (i, j)（i < j），计算前一个元素 a：

   a = 2 * nums[i] - nums[j]

   该公式基于等差数列的性质：若 a, b, c 成等差数列，则 2b = a + c，即 a = 2b - c

2. 若 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; }}

填表顺序

1. 外层循环遍历 i 从 1 到 n-1（当前倒数第二个元素的索引）

2. 内层循环遍历 j 从 i+1 到 n-1（当前最后一个元素的索引）

3. 对于每个 (i, j) 对，检查是否存在满足条件的 a，并更新状态

4. 在处理完当前 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> hash = new HashMap(); for(int i = 0; i < n; i++){ long tmp = (long)nums[i]; if(!hash.containsKey(tmp))  hash.put(tmp, new ArrayList()); 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] 为末尾的等差数列的数量

状态转移方程

1. 对于每个元素对 (i, j)（i < j），计算前一个元素 a：

   a = 2 * nums[i] - nums[j]

   该公式基于等差数列的性质：若 a, b, c 成等差数列，则 2b = a + c

2. 若 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，表示没有找到等差数列

填表顺序

1. 外层循环遍历 j 从 2 到 n-1（确保至少有三个元素）

2. 内层循环遍历 i 从 1 到 j-1（确保 i < j）

3. 对于每个 (i, j) 对，计算 a = 2 * nums[i] - nums[j]，并检查哈希表中是否存在 a

4. 若存在，遍历所有 a 的索引 k（按升序排列），当 k < i 时更新 dp[i][j]

5. 将 dp[i][j] 的值累加到结果 ret 中

返回值计算

• 在遍历过程中累加所有 dp[i][j] 的值，最终返回 ret

算法复杂度分析

• 时间复杂度：O(n²)

  • 两层嵌套循环遍历所有元素对 (i, j)

  • 哈希表操作时间复杂度为 O (1)，但最坏情况下可能遍历所有 a 的索引

• 空间复杂度：O(n²)

  • 主要用于存储二维 dp 数组和哈希表