当前位置：首页 > news >正文

每日练题之动态规划（子序列问题讲解 1.最长递增子序列 2.摆动序列）

news 来源：原创 2025/7/24 3:37:01

前言：

需要对「子序列」和「子数组」这两个概念进行区分；

子序列（subsequence）：子序列并不要求连续，但是我们调出来的顺序必须和原数组的顺序相同。例如：序列 [4, 6, 5] 是 [1, 2, 4, 3, 7, 6, 5] 的一个子序列；
子数组（substring、subarray）：子串一定是原始字符串的连续子串。

「上升」的意思是「严格上升」。反例： [1, 2, 2, 3] 不能算作「上升子序列」；
子序列中元素的相对顺序很重要，子序列中的元素必须保持在原始数组中的相对顺序。如果把这个限制去掉，将原始数组去重以后，元素的个数即为所求；

子序列问题的一般做题步骤：

步骤概述：

定义状态（状态转移方程）
动态规划首先需要明确问题的状态（通常是一个二维或一维数据库）。状态数据库dp[i]表示到达位置i时的最优化解（例如最小/顶点、最短/终止路径等））。
填表
根据状态转移方程，通过自下而上的方式进行dp内存填充，每个初始子问题的最优化解。
逆推最后一个子序列
一旦dp表单状态填充完成，通常需要从dp最终形成（例如dp[n-1]，这里的n可能是吞吐量的长度或其他标志性参数）开始，逆推找到最终解的子序列。

具体操作步骤：

1.定义状态和状态转移方程

假设我们在解决一个典型的动态规划问题，比如终止递增子序列（LIS）问题。我们定义一个队列dp，其中dp[i]以第i一个元素代表终止的终止递增子序列的长度。状态移位方程如下：

dp[i] = max(dp[j] + 1)，其中0 <= j < i且arr[j] < arr[i]。

2. 填充状态

根据状态转移方程，自底向上填充dp队列，最终得到递增子序列的长度。假设dp[n-1]表示到达队列最后一个元素时的最优解。

3. 逆推得到子序列

一旦我们知道了dp阵列中的最优值，接下来就是逆推回去，找到具体的子序列。例如：

从最后一个元素开始：找到dp顶点中的对应索引，假设是i，即我们从arr[i]开始。
找到前面的一个元素：逆推找到前面的一个元素arr[j]，arr[j] < arr[i]且使得dp[j] == dp[i] - 1。这样就可以把arr[j]加入到子序列中。
重复这个过程：继续沿着dp阵列逆推，直到找到整个子序列。

1.题目讲解

300. 最长递增子序列
376. 摆动序列

1. 最长递增子序列

1.题目解析

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

2.讲解算法原理

1.状态表示：

dp[i] : 表示当我们到达i位置时得到的最长递增子序列。

2.状态转移表示：

我们的dp[i]有两种表示：

1.当数组长度为1时：dp[i] = 1;

2.当数组长度不为1时：

我们以i位置为结尾时：因为子序列 是由数组派生而来的序列，：子序列并不要求连续，但是我们调出来的顺序必须和原数组的顺序相同。例如：序列 [4, 6, 5] 是 [1, 2, 4, 3, 7, 6, 5] 的一个子序列；但是：序列 [4, 6, 5]不是严格按照递增。

所以要找到严格递增的话，我们必须需要让我们后一个值大于前一个值，又因为我们不只是锁定为从0下标位置开始找最长子序列，这个值可以是数组的任意一个下标。

例如示例1：

nums = [10,9,2,5,3,7,101,18]

从2 开始找而不是从10开始，由此我们可以得出当我们以 i 下标为结尾时，我们要找到 i - 1下标的状态：

					i

他前面的值我们总体用J来表示：即：0<= j <= i - 1 位置的值，如果num[ i ] (后一项) > num[j](前一项) 我们就让这个值+1，求出最大之即可

3.初始化

表里面的所有值初始化为 1

4.填表顺序

从左往右

5.返回值

dp 表里面的最大值

3.编写代码

2.摆动序列

1.题目解析

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

2.讲解算法原理

1.状态表示：

第一次分析：

dp[i] 表示为 i 位置的元素为结尾的最大湍流子数组的长度；

当我们只定义一个状态表示时，我们会发现用它表示时dp[i -1]的数字有两种状态

1.比后一位大 2.比前一位小所以不行

第二次分析：

因为dp[i]的前一位有两种表现形式，所以我们要定义两种状态表示

f[i] 表示:以ì位置元素为结尾的所有的子序列中，最后一个位置呈现"上升"趋势的最长摆动序列的长度
g[i] 表示:以i位置元素为结尾的所有的子序列中，最后一个位置呈现“下降”趋势的最长摆动序列的长度
2.状态转移方程;
0 1 2 ...... i-2 i-1 i
b a

1.当最后一位呈现“上升”状态的情况分析：

1.当数组长度为1时：f[i] = 1;

2.当数组长度不为1时：num[ i ] (后一项) > num[j] (前一项) 时 f[i] = Math.max(g[i -1] +1,f[i]);

2.当最后一位呈现“下降”状态的情况分析：

1.当数组长度为1时：g[i] = 1;

2.当数组长度不为1时：num[ i ] (后一项) < num[j] (前一项) 时 g[i] =Math.max( f[i -1] +1,g[i]);

3.初始化:

1.因为只有一个元素时，长度为一，所以我们把初始值都设为一，即可省略为1的这种情况，

4.填表顺序：

从左往右，两个表一起填

5.返回值：

F表和G表里的最大值.

3.编写代码

总结：

子序列问题和子数组问题大致的思路方式是不变的，如果碰到相类似的题我们就可以按部就班，想我们前几天做的题，就可以完美解决问题，如果一个状态表示不够我们就可以定义多个状态表示来解决问题；

下期预告：

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

感兴趣的小伙伴们可以先看看题呦，一起加油！！！

前言：

子序列问题的一般做题步骤：

步骤概述：

具体操作步骤：

1.定义状态和状态转移方程

2. 填充状态

3. 逆推得到子序列

1.题目讲解

1. 最长递增子序列

1.题目解析

2.讲解算法原理

1.状态表示：

2.状态转移表示：

3.初始化

4.填表顺序

5.返回值

3.编写代码

2.摆动序列

1.题目解析

2.讲解算法原理

1.状态表示：

3.初始化:

4.填表顺序：

5.返回值：

3.编写代码

总结：

下期预告：

相关文章：