一、解题心得

首先子序列是不连续的，所以一定不会在 i - 1 位置去推 i 位置的 dp 值了，所以一般子序列问题是 O(n^2) 复杂度。但是可以通过哈希表等方式降成 O(n)。

以我带来的例题其实子序列问题可以分成两种：

1、以 i 位置为结尾，....

这种是一维 dp，固定了序列的最后一个数 nums[i] 就能固定这个序列的大致情况，此时要填 dp[i] 就要根据 [0, i - 1] 位置的数，所以是 O(n^2) 复杂度。

固定 i 搜索 [0, i - 1] 的 j，用 dp[j] 更新 dp[i]

2、以 i j 位置为结尾，...

这种是二维 dp，只固定最后一个数不能确定一个序列，但是固定最后两个数就行，此时由于是最后两个数 nums[i], nums[j]，所以第三个数的下标一定小于 i，此时用倒数第三和倒数第二的 dp 表更新 dp[i] 即可。

固定 i j 搜索 [0, i - 1] 的 k，用哈希表优化掉 k 的下标搜索，用 dp[k][i] 更新 dp[i][j]

所以 dp 问题还是一个核心：你的维数一定要能表示或确定所有的情况，才能解决问题，接下来的只不过是如何写出状态转移方程和优化。

二、例题

1、最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

最后一个和 j 比较就能确定序列，所以一维。

2、摆动序列

376. 摆动序列 - 力扣（LeetCode）

最后一个和 j 比较就能确定序列，所以一维。

为了表示方便最好能细分情况就细分。

3、最长递增子序列个数

673. 最长递增子序列的个数 - 力扣（LeetCode）

发现一个一维确实表示不了所有情况，但是第二个需求是存个数，一个结尾只有一个个数，所以没必要二维，两个一维就能解决问题。

4、最长数对链

646. 最长数对链 - 力扣（LeetCode）

最后一个和前面一个比较就能确定序列，所以一维就行。

5、最长定差子序列

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

本来等差数列问题确实只知道最后一个数不能确定整个序列，因为公差不同。但是这道题告诉你公差了，所以一维就行。

而且只要知道最长长度，所以只要找到最接近 nums[i] 的 nums[[k] 即可，所以用哈希表处理最接近nums[i] 的 nums[[k] 的下标 k搜索，但是如果数列中是有重复数那哈希表只能边 dp 边更新。

6、最长斐波那契子序列长度

873. 最长的斐波那契子序列的长度 - 力扣（LeetCode）

由于数列严格递增，所以哈希表一开始就能存下标。

7、最长等差数列

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

首先是求长度，所以要找最接近 nums[i] 的 nums[k]，其次有重复值，所以哈希表边 dp 边更新。

8、等差数列子序列个数

446. 等差数列划分 II - 子序列 - 力扣（LeetCode）

首先求的是个数，所以不是找最接近 nums[i] 的 nums[k]，而是所有的 nums[k]，这时哈希表存的是 <int, vector<int>>，其次虽然还是确保 k < i，理应是哈希表边 dp 边更新，但是存的是 vector<int> 并且循环里面判断 k < i，所以直接存下标也可以。