例题一
解法（动态规划）：
算法思路：
1.
状态表⽰：
对于线性
dp
，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
i.
以某个位置为结尾，巴拉巴拉；
ii.
以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：
dp[i]
表⽰：以
i
位置元素为结尾的「所有⼦序列」中，最⻓递增⼦序列的⻓度。
2.
状态转移⽅程：
对于 dp[i] ，我们可以根据「⼦序列的构成⽅式」，进⾏分类讨论：
i.
⼦序列⻓度为 1 ：只能⾃⼰玩了，此时 dp[i] = 1
；
ii.
⼦序列⻓度⼤于 1 ：
nums[i]
可以跟在前⾯任何⼀个数后⾯形成⼦序列。
设前⾯的某⼀个数的下标为
j ，其中 0 <= j <= i - 1
。只要 nums[j] < nums[i] ， i
位置元素跟在
j 元素后⾯就可以形成递增序列，⻓度为 dp[j] + 1
。因此，我们仅需找到满⾜要求的最⼤的 dp[j] + 1 即可。 综上， dp[i] = max(dp[j] + 1, dp[i]) ，其中
0 <= j <= i - 1 && nums[j] < nums[i] 。
3.
初始化：
所有的元素「单独」都能构成⼀个递增⼦序列，因此可以将
dp
表内所有元素初始化为
1
。由于⽤到前⾯的状态，因此我们循环的时候从第⼆个位置开始即可。
4.
填表顺序：
显⽽易⻅，填表顺序「从左往右」。
5.
返回值：
由于不知道最⻓递增⼦序列以谁结尾，因此返回
dp
表⾥⾯的「最⼤值」。
例题二
解法（动态规划）：
算法思路：
1.
状态表⽰：
对于线性
dp
，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
i.
以某个位置为结尾，巴拉巴拉；
ii.
以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：dp[i] 表⽰「以
i
位置为结尾的最⻓摆动序列的⻓度」。但是，问题来了，如果状态表⽰这样定义的话，以 i
位置为结尾的最⻓摆动序列的⻓度我们没法从之前的状态推导出来。因为我们不知道前⼀个最⻓摆动序列的结尾处是递增的，还是递减的。因此，我们需要状态表⽰能表⽰多⼀点的信息：要能让我们知道这⼀个最⻓摆动序列的结尾是递增的还是递减的。解决的⽅式很简单：搞两个 dp
表就好了。
f[i]
表⽰：以 i 位置元素为结尾的所有的⼦序列中，最后⼀个位置呈现「上升趋势」的最⻓摆动序列的⻓度；
g[i]
表⽰：以 i 位置元素为结尾的所有的⼦序列中，最后⼀个位置呈现「下降趋势」的最⻓摆动序列的⻓度。
2.
状态转移⽅程：
由于⼦序列的构成⽐较特殊，
i
位置为结尾的⼦序列，前⼀个位置可以是
[0, i - 1]
的任意位置，因此设 j
为
[0, i - 1]
区间内的某⼀个位置。
对于f[i] ，我们可以根据「⼦序列的构成⽅式」，进⾏分类讨论：
i.
⼦序列⻓度为 1 ：只能⾃⼰玩了，此时 f[i] = 1
；
ii.
⼦序列⻓度⼤于1 ：因为结尾要呈现上升趋势，因此需要
nums[j] < nums[i]
。在满⾜这个条件下， j
结尾需要呈现下降状态，最⻓的摆动序列就是
g[j] + 1
。因此我们要找出所有满⾜条件下的最⼤的g[j] + 1 。综上， f[i] = max(g[j] + 1, f[i]) ，注意使⽤g[j] 时需要判断。
对于g[i] ，我们可以根据「⼦序列的构成⽅式」，进⾏分类讨论：
i.
⼦序列⻓度为 1 ：只能⾃⼰玩了，此时 g[i] = 1
；
ii.
⼦序列⻓度⼤于 1 ：因为结尾要呈现下降趋势，因此需要
nums[j] > nums[i]
。在满⾜这个条件下， j
结尾需要呈现上升状态，因此最⻓的摆动序列就是
f[j] + 1
。因此我们要找出所有满⾜条件下的最⼤的f[j] + 1 。 综上， g[i] = max(f[j] + 1, g[i]) ，注意使⽤f[j] 时需要判断。
3.
初始化：
所有的元素「单独」都能构成⼀个摆动序列，因此可以将
dp 表内所有元素初始化为 1
。
4.
填表顺序：
毫⽆疑问是「从左往右」。
5.
返回值：
应该返回「两个
dp
表⾥⾯的最⼤值」，我们可以在填表的时候，顺便更新⼀个「最⼤值」。
例题三
解法（动态规划）：
算法思路：
1.
状态表⽰：
先尝试定义⼀个状态：以
i
为结尾的最⻓递增⼦序列的「个数」。那么问题就来了，我都不知道
以
i
为结尾的最⻓递增⼦序列的「⻓度」是多少，我怎么知道最⻓递增⼦序列的个数呢？因此，我们解决这个问题需要两个状态，⼀个是「⻓度」，⼀个是「个数」：
len[i]
表⽰：以
i
为结尾的最⻓递增⼦序列的⻓度；
count[i]
表⽰：以
i
为结尾的最⻓递增⼦序列的个数。
2.
状态转移⽅程：
求个数之前，我们得先知道⻓度，因此先看
len[i]
：
i.
在求 i
结尾的最⻓递增序列的⻓度时，我们已经知道
[0, i - 1]
区间上的
len[j]信息，⽤ j
表⽰
[0, i - 1]
区间上的下标；
ii.
我们需要的是递增序列，因此 [0, i - 1]
区间上的
nums[j]
只要能和
nums[i]构成上升序列，那么就可以更新 dp[i]
的值，此时最⻓⻓度为
dp[j] + 1
；
iii.
我们要的是 [0, i - 1]
区间上所有情况下的最⼤值。
综上所述，对于
len[i]
，我们可以得到状态转移⽅程为：
len[i] = max(len[j] + 1, len[i])
，其中
0 <= j < i
，并且
nums[j] < nums[i] 。
在知道每⼀个位置结尾的最⻓递增⼦序列的⻓度时，我们来看看能否得到
count[i]
：
i.
我们此时已经知道 len[i]
的信息，还知道
[0, i - 1]
区间上的
count[j]
信息，⽤ j
表⽰
[0, i - 1]
区间上的下标；
ii.
我们可以再遍历⼀遍 [0, i - 1]
区间上的所有元素，只要能够构成上升序列，并且上升序列的⻓度等于 dp[i]
，那么我们就把
count[i]
加上
count[j]
的值。这样循环⼀遍之后， count[i]
存的就是我们想要的值。
综上所述，对于
count[i]
，我们可以得到状态转移⽅程为：
count[i] += count[j]
，其中
0 <= j < i
，并且
nums[j] < nums[i] && dp[j] + 1 == dp[i] 。
3.
初始化：
◦
对于 len[i] ，所有元素⾃⼰就能构成⼀个上升序列，直接全部初始化为
1
；
◦
对于 count[i] ，如果全部初始化为 1 ，在累加的时候可能会把「不是最⼤⻓度的情况」累加进去，因此，我们可以先初始化为 0 ，然后在累加的时候判断⼀下即可。具体操作情况看代码~
4.
填表顺序：
毫⽆疑问是「从左往右」。
5.
返回值：
⽤
lenmax
表⽰最终的最⻓递增⼦序列的⻓度。
根据题⽬要求，我们应该返回所有⻓度等于 l
enmax
的⼦序列的个数。
例题四
解法（动态规划）：
算法思路：
这道题⽬让我们在数对数组中挑选出来⼀些数对，组成⼀个呈现上升形态的最⻓的数对链。像不像
我们整数数组中挑选⼀些数，让这些数组成⼀个最⻓的上升序列？因此，我们可以把问题转化成我
们学过的⼀个模型：
300. 最⻓递增⼦序列
。因此我们解决问题的⽅向，应该在「最⻓递增⼦序
列」这个模型上。不过，与整形数组有所区别。在⽤动态规划结局问题之前，应该先把数组排个序。因为我们在计算 dp[i]
的时候，要知道所有左区间⽐
pairs[i]
的左区间⼩的链对。排完序之后，只⽤「往前遍历⼀遍」即可。
1.
状态表⽰：
dp[i]
表⽰以
i
位置的数对为结尾时，最⻓数对链的⻓度。
2.
状态转移⽅程：
对于
dp[i]
，遍历所有
[0, i - 1]
区间内数对⽤
j
表⽰下标，找出所有满⾜ pairs[j][1] < pairs[i][0] 的
j
。找出⾥⾯最⼤的
dp[j]
，然后加上
1
，就是以
i 位置为结尾的最⻓数对链。
3.
初始化：
刚开始的时候，全部初始化为
1
。
4.
填表顺序：
根据「状态转移⽅程」，填表顺序应该是「从左往右」。
5.
返回值：
根据「状态表⽰」，返回整个
dp
表中的最⼤值。
例题五
解法（动态规划）：
算法思路：
这道题和
300. 最⻓递增⼦序列
有⼀些相似，但仔细读题就会发现，本题的
arr.lenght
⾼达10^5 ，使⽤
O(N^2)
的
lcs
模型⼀定会超时。
那么，它有什么信息是
300. 最⻓递增⼦序列
的呢？是定差。之前，我们只知道要递增，不知道前
⼀个数应当是多少；现在我们可以计算出前⼀个数是多少了，就可以⽤数值来定义
dp
数组的值，并形成状态转移。这样，就把已有信息有效地利⽤了起来。
1.
状态表⽰：
dp[i]
表⽰：以
i
位置的元素为结尾所有的⼦序列中，最⻓的等差⼦序列的⻓度。
2.
状态转移⽅程：
对于
dp[i]
，上⼀个定差⼦序列的取值定为
arr[i] - difference
。只要找到以上⼀个数字为结尾的定差⼦序列⻓度的 dp[arr[i] - difference]
，然后加上
1
，就是以
i
为结尾的定差⼦序列的⻓度。因此，这⾥可以选择使⽤哈希表做优化。我们可以把「元素， dp[j]
」绑定，放进哈希表中。甚⾄不⽤创建 dp
数组，直接在哈希表中做动态规划。
3.
初始化：
刚开始的时候，需要把第⼀个元素放进哈希表中，
hash[arr[0]] = 1
。
4.
填表顺序：
根据「状态转移⽅程」，填表顺序应该是「从左往右」。
5.
返回值：
根据「状态表⽰」，返回整个
dp
表中的最⼤值。
例题六
解法（动态规划）：
算法思路：
1.
状态表⽰：
对于线性
dp
，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
i.
以某个位置为结尾，巴拉巴拉；
ii.
以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：
dp[i]
表⽰：以
i
位置元素为结尾的「所有⼦序列」中，最⻓的斐波那契⼦数列的⻓度。
但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定 i 结尾的斐波那契序列的样⼦。这样就会导
致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个斐波那契序列。根据斐波那契数列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。因此，我们修改我们的状态表⽰为：
dp[i][j]
表⽰：以 i 位置以及
j
位置的元素为结尾的所有的⼦序列中，最⻓的斐波那契⼦序列的⻓度。规定⼀下 i < j 。
2.
状态转移⽅程：
设 nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是
a = c - b
。我们根据 a的情况讨论：
i.
a 存在，下标为
k
，并且
a < b
：此时我们需要以
k
位置以及
i
位置元素为结尾的最⻓斐波那契⼦序列的⻓度，然后再加上 j
位置的元素即可。于是
dp[i][j] = dp[k][i] + 1 ；
ii.
a 存在，但是
b < a < c
：此时只能两个元素⾃⼰玩了，
dp[i][j] = 2
；
iii.
a
不存在：此时依旧只能两个元素⾃⼰玩了，
dp[i][j] = 2
。
综上，状态转移⽅程分情况讨论即可。
优化点：我们发现，在状态转移⽅程中，我们需要确定
a
元素的下标。因此我们可以在
dp
之前，将所有的「元素 + 下标」绑定在⼀起，放到哈希表中。
3.
初始化：
可以将表⾥⾯的值都初始化为
2
。
4.
填表顺序：
a.
先固定最后⼀个数；
b.
然后枚举倒数第⼆个数。
5.
返回值：
因为不知道最终结果以谁为结尾，因此返回
dp
表中的最⼤值
ret
。但是 ret
可能⼩于
3
，⼩于
3
的话说明不存在。因此需要判断⼀下。
例题七
解法（动态规划）：
算法思路：
1.
状态表⽰：
对于线性
dp
，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
i.
以某个位置为结尾，巴拉巴拉；
ii.
以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：dp[i] 表⽰：以
i
位置元素为结尾的「所有⼦序列」中，最⻓的等差序列的⻓度。但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定 i
结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列。根据等差序列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。因此，我们修改我们的状态表⽰为：
dp[i][j]
表⽰：以
i
位置以及
j
位置的元素为结尾的所有的⼦序列中，最⻓的等差序列的⻓度。规定⼀下 i < j
。
2.
状态转移⽅程：
设nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是
a =2 * b - c
。我们根据a的情况讨论：
a.
a 存在，下标为
k
，并且
a < b
：此时我们需要以
k
位置以及
i
位置元素为结尾的最⻓等差序列的⻓度，然后再加上 j
位置的元素即可。于是
dp[i][j] = dp[k][i] + 1 。这⾥因为会有许多个
k
，我们仅需离
i
最近的
k
即可。因此任何最⻓的都可以以
k为结尾；
b.
a
存在，但是
b < a < c
：此时只能两个元素⾃⼰玩了，
dp[i][j] = 2
；
c.
a
不存在：此时依旧只能两个元素⾃⼰玩了，
dp[i][j] = 2
。
综上，状态转移⽅程分情况讨论即可。
优化点：我们发现，在状态转移⽅程中，我们需要确定
a
元素的下标。因此我们可以将所有的元素 + 下标绑定在⼀起，放到哈希表中，这⾥有两种策略：
a.
在 dp
之前，放⼊哈希表中。这是可以的，但是需要将下标形成⼀个数组放进哈希表中。这样时间复杂度较⾼，我帮⼤家试过了，超时。
b.
⼀边 dp
，⼀边保存。这种⽅式，我们仅需保存最近的元素的下标，不⽤保存下标数组。但是⽤这种⽅法的话，我们在遍历顺序那⾥，先固定倒数第⼆个数，再遍历倒数第⼀个数。这样就可以在 i
使⽤完时候，将
nums[i]扔到哈希表中。
3.
初始化：
根据实际情况，可以将所有位置初始化为 2 。
4.
填表顺序：
a.
先固定倒数第⼆个数；
b.
然后枚举倒数第⼀个数。
5.
返回值：
由于不知道最⻓的结尾在哪⾥，因此返回dp 表中的最⼤值。
例题八
解法（动态规划）：
算法思路：
1.
状态表⽰：
对于线性
dp
，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰：
i.
以某个位置为结尾，巴拉巴拉；
ii.
以某个位置为起点，巴拉巴拉。
这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：
dp[i] 表⽰：以
i
位置元素为结尾的「所有⼦序列」中，等差⼦序列的个数。
但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定
i
结尾的等差序列的样⼦。这样就会导致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个等差序列。根据等差序列的特性，我们仅需知道序列⾥⾯的最后两个元素，就可以确定这个序列的样⼦。因此，我们修改我们的状态表⽰为：
dp[i][j]
表⽰：以
i
位置以及
j
位置的元素为结尾的所有的⼦序列中，等差⼦序列的个数。规定⼀下 i < j
。
2.
状态转移⽅程：
设nums[i] = b, nums[j] = c ，那么这个序列的前⼀个元素就是
a =2 * b - c
。我们根据a的情况讨论：
a.
a 存在，下标为
k
，并且
a < b
：此时我们知道以
k
元素以及
i
元素结尾的等差序列的个数 dp[k][i]
，在这些⼦序列的后⾯加上
j
位置的元素依旧是等差序列。但是这⾥会多出来⼀个以 k, i, j
位置的元素组成的新的等差序列，因此
dp[i][j] = dp[k][i] + 1 ；
b.
因为
a
可能有很多个，我们需要全部累加起来。
综上， dp[i][j] += dp[k][i] + 1
。
优化点：我们发现，在状态转移⽅程中，我们需要确定
a
元素的下标。因此我们可以在 dp 之前，将所有元素 + 下标数组绑定在⼀起，放到哈希表中。这⾥为何要保存下标数组，是因为我们要统计个数，所有的下标都需要统计。
3.
初始化：
刚开始是没有等差数列的，因此初始化
dp
表为
0
。
4.
填表顺序：
a.
先固定倒数第二个数；
b.
然后枚举倒数第一个数。
5.
返回值：
我们要统计所有的等差⼦序列，因此返回
dp
表中所有元素的和。
![NSSCTF | [SWPUCTF 2021 新生赛]easyupload2.0](https://img-blog.csdnimg.cn/direct/e7365ddaee994c438241ceeb7eab363d.png)
