给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
解题思路
子序列的问题和子串的最大不同就在于子序列是不连续的，我们之前遇到的子串问题则是连续的，所以可以通过 i-1 来获得之前的所有连续子串的可能，但是现在子序列则不同了，我们不光光要通过 i-1 来推导 i，得通过**【0，……，i-1】**的所有可能来推导 i，这就是和子串问题的不同之处，可以看出我们就得在推导 i 的时候再去遍历一遍 i 之前的所有可能的最值，这无疑提高了时间复杂度！
但是分析动态规划问题，还是分为以下几个步骤：
- 状态表示
- “经验 + 题目要求”：以某处为结尾然后……的情况
- 所以可以设定 dp[i] 表示以 i 结尾的所有子序列中，最大的递增序列长度
- 状态转移方程
- 对于子序列的题来说，依旧可以分为两种情况：
- 子序列长度为1：很明显长度为 1 就是当前 nums[i] 本身，那么根据题目规定 dp[i] = 1
- 子序列长度大于1：此时 nums[i] 可以跟在前面的任何一个数形成新的子序列，也就是说 i 处的元素可以和**【0，……，i-1】**的数形成新的子序列。
- 这里设前面的某个数的下标为 j，那么 j 的 范围就是
[0, i-1]，此时只要满足了题目要求：nums[j] < nums[i]，那么就说明它们能构成一个递增的序列，长度就是dp[j] + 1，表示原先以 j 结尾的最大递增子序列加上 nums[i] 后形成的新的最大递增子序列的长度！ - 因此我们只要找到所有的 dp[j]+1 中最大的那个，赋值给 dp[i] 即可，但是前提要满足递增！
- 这里设前面的某个数的下标为 j，那么 j 的 范围就是
- 对于子序列的题来说，依旧可以分为两种情况：
- 初始化
- 所有的元素「单独」都能构成⼀个递增子序列，因此可以将 dp 表内所有元素初始化为 1。由于用到前面的状态，因此我们循环的时候从第⼆个位置开始即可。
- 填表顺序
- 从左往右填表
- 返回值
- 由于不知道最长递增子序列以谁结尾，因此返回 dp 表里面的「最大值」
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// 创建dp表
int n = nums.size();
vector<int> dp(n, 1); // 都初始化为1
int ret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[i] > nums[j]) // 满足递增才去更新dp[i]
{
dp[i] = max(dp[j] + 1, dp[i]); // 只取最大的那个更新dp[i]
}
}
ret = max(ret, dp[i]); // 获取途中最大的dp[i]
}
return ret;
}
};2、摆动序列（medium）
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
解题思路
这道题其实和上一道题是类似的，状态表示和状态转移方程解析如下：
对于初始化来说，题目规定一个元素也是一个长度单位，所以我们将两个数组都初始化为 1 即可！
对于返回值问题，因为最长摆动序列长度不一定是在结尾拿到，所以遍历的途中要顺便记录下两种情况的最值，最后返回这个最值即可！
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
// 创建dp表，都初始化为1
int n = nums.size();
vector<int> up(n, 1);
vector<int> down(n, 1);
int ret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
// 对于等于0的情况不用关心
if(nums[i] - nums[j] > 0)
up[i] = max(up[i], down[j] + 1);
else if(nums[i] - nums[j] < 0)
down[i] = max(down[i], up[j] + 1);
}
ret = max(ret, max(up[i], down[i])); // 取途中遇到的最大值
}
return ret;
}
};优化
其实这道题是可以优化一下的，从这个过程图可以很形象的说明整个过程：
可以看到，其实这种方式相比于上面那种方式，只需要我们遍历一次状态，因为此时其实我们只需要考虑 i 与 i-1 的关系，因为我们有两个状态来表示，如果一直是递增的话，另一个状态的值一直都是某个值，而更新的那个状态则会一直用这个不变的状态值去更新，结果还是不变的，只有当这个序列是摆动的时候，更新才会迭代起来，这是得益于用两种状态表示的结果！
并且我们其实是可以用两个变量就记录这个状态值的，因为只有摆动才会更新，如果不摆动，其中一个状态用的一直都是另一个无关当前状态的值，所以长度是不会增长的，具体参考上面的过程图！
这样子我们又把时间复杂度变成了 O(n)，空间复杂度还变成了 O(1)，比上面的方法高效许多！
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int up = 1, down = 1; // 直接用两个变量来记录序列长度
for(int i = 1; i < n; ++i)
{
if(nums[i] - nums[i - 1] > 0)
up = down + 1;
else if(nums[i] - nums[i - 1] < 0)
down = up + 1;
}
return max(up, down);
}
};3、最长递增子序列的个数（medium）
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。提示:
1 <= nums.length <= 2000-106 <= nums[i] <= 106
解题思路
这道题其实就是第一道题的变形，加入了在途中记录最大长度的出现次数，其实我们可以从一道我们经常遇到的题入手：
就是求一个无序的数组中最大值出现的次数，其实我们遍历一遍就能拿到这个出现的次数了，只要我们定义两个变量，一个用来记录遇到的最大值 maxval，一个用来记录这个最大值出现的次数 count。当遇到更大的数的时候，则更新最大值，出现次数也重新统计；当遇到相等的数时，出现次数加一；当遇到比当前最大值小的数的时候，则无需处理。这样子一来遍历完数组之后就能通过 count 变量直接拿到最大值的出现次数！
为什么要先介绍这个题呢，因为其实道理是一样的，这道题我们为了时间复杂度小点，可以在遍历过程中就记录下最长子序列的出现次数，只不过对于这道题来说，从刚才的求一个数，变成了求一个序列罢了！
首先是状态表示，很明显，这道题用一个状态是搞不定的，因为如果我们让 dp[i] 表示以 i 结尾的所有子序列中最长递增子序列的出现次数，那么我们会发现在推导的时候我们需要 i 位置之前的最长递增子序列的长度，所以一个状态搞不定，我们不能这么设定状态表示！
简单地说，这个状态表示中，包含了两个需要推导的因素：长度 + 次数，所以我们用两个 dp 表来表示：
- lenDP[i]：表示以 i 结尾的所有子序列中，最长递增子序列的长度
- countDP[i]：表示以 i 结尾的所有子序列中，最长递增子序列的出现的次数
**对于状态转移方程的推导，其实不要想的太复杂，就是在第一道题的基础之上，我们要多两步去判断并且更新出现次数而已！**对于长度的推导，这里就不赘述了，具体可以参考第一道题的题解，这里主要解释加入了判断次数的情况！
对于下面的推导中，我们依然使用下标 j 来表示**【0, i-1】范围，表示的是 i 位置前的所有下标范围。我们要想，什么情况下需要我们去更新出现次数，无非就是三种情况**：
- 出现了更长的递增子序列也就是
lenDP[j] + 1 > lenDP[i]：既需要更新出现次数，也需要更新最长递增子序列的长度。- 此时出现次数肯定就变成了这个更长的递增子序列的出现次数，也就是
countDP[i] = countDP[j]，而最长递增子序列的长度就变成了countDP[i] = lenDP[j] + 1，因为还要加上 i 处当前元素本身的长度，而出现次数则不需要！
- 此时出现次数肯定就变成了这个更长的递增子序列的出现次数，也就是
- 出现了等长的递增子序列
lenDP[j] + 1 == lenDP[i]：此时只需要更新出现次数。- 因为最长递增子序列的长度不变，但是注意这里是要累加上出现次数，而不是把出现次数覆盖掉了，所以最终得到
countDP[i] += countDP[j]。
- 因为最长递增子序列的长度不变，但是注意这里是要累加上出现次数，而不是把出现次数覆盖掉了，所以最终得到
- 出现了更短的递增子序列：这种情况不需要我们去处理，直接忽略就行
💥注意上面说的三种情况，都是建立在递增的基础上！
接下来就是初始化问题，我们只需要让两个 dp 表都初始化为 1 即可，因为如果当前元素本身就是长度为 1 的递增子序列，而且出现次数为 1。
填表顺序的话就是从左往右，每次再去遍历 i 前面的所有情况即可，时间复杂度为 O(n)。
对于返回值问题，我们之前的题目也说过了，最后的结果不一定是最大值，所以我们必须在遍历途中就记录下最值，这里需要记录俩个，一个是长度最大值 lenret，一个是出现次数最大值 countret。
每次我们遍历完 i 前面的所有子序列可能，也就是得到了 lenDP[i] 和 countDP[i] 之后，我们就对 lenret 和 countret 进行判断更新！和上面状态转移方程是一样的，也是考虑两种情况（长度变小的不考虑）：
lenDP[i] > lenret：说明此时遇到长度更大的递增子序列，需要更新长度和出现次数，此时lenret = lenDP[i]，而countret = countDP[i]。lenDP[i] == lenret：说明此时长度是一样的，所以只要累加出现次数即可，注意是累加，不是覆盖长度，所以countret += countDP[i]。
最后返回得到的 countret 即可！
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
// 创建两个dp表，都初始化为1
int n = nums.size();
vector<int> lendp(n, 1);
vector<int> countdp(n, 1);
int lenret = 1, countret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
// 只有递增才处理
if(nums[i] > nums[j])
{
if(lendp[j] + 1 > lendp[i]) // 长度更新最大的话，重新统计局部的出现次数，更新为更长递增子序列的出现次数
{
countdp[i] = countdp[j];
lendp[i] = lendp[j] + 1; // 顺便更新一下局部最大长度
}
else if(lendp[j] + 1 == lendp[i]) // 长度如果相等，则局部的出现次数累加上这次的出现次数
{
countdp[i] += countdp[j];
}
}
}
// 判断是否需要更新全局的
if(lendp[i] > lenret)
{
// 如果lendp[i]大于全局最长的子序列的话，则出现次数变成新的最长子序列出现次数countdp[i]
countret = countdp[i];
lenret = lendp[i]; // 顺便更新一全局的最大长度
}
else if(lenret == lendp[i])
{
// 如果lendp[i]等于全局最长的子序列，那么要累加一下lendp[i]出现的次数也就是countdp[i]
countret += countdp[i];
}
}
return countret;
}
};4、最长数对链（medium）
给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 1：
输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。示例 2：
输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。提示：
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000
解题思路
这道题其实也是最长递增子序列的一个变型，可以看到上面的示例 2 中，最长的长度其实是 3，如下图：
可以看到，如果我们不做预处理的话，我们的状态其实不是那么好表示，因为一般我们都是设某处为结尾然后……的情况，但是这种假设是基于某处只能被它前面的元素推导出来，但是这道题最大的不同之处就是一个数链它可以以任何顺序选择其中的一些数对来构造，也就是说某处既可能被前面推导，又被后面元素推导，这并不符合动态规划的思想，所以必须做一下预处理！
其实预处理很简单，就是排序，但是我们在排序的时候，要严格按照不出现递减的情况（因为也有相等的情况），假设这里有三个子数组 v1、v2，它们分别是 [4, 8]、[1, 9]。
此时如果我们只是按照两个数组中间也就是 vi 的尾元素和 vi+1 的头元素来比较的话，最后排序出来就是这样子的：[1, 9]、[4, 8]，此时就不对了，因为它们中间的两个元素还是一样不符合序列，简单地说，就是我们的排序一定要严格按照不出现递减的情况，所以我们必须要用 vi 的头元素和 vi+1 的头元素来比较，如果 vi+1 的头元素都大于 vi 的头元素，那么肯定大于 vi 的尾元素，就能保证两个数组之间的次序！
而因为这道题用的是 vector，我们在使用 std::sort 的时候，其实不用去加上什么比较器，因为此时 std::sort(v.begin(), v.end()) 这个函数如果比较的元素是 vector 的话，其实默认比较的就是两个 vector 的第一个元素！
对于状态表示、状态转移方程、初始化和返回值这些问题，都不是这道题的重点，可以参考最长递增子序列的做法，一模一样，只不过更新的条件变了一下，变成了题目要求的两个数组中间的元素判断是递增序列，这个并不难，具体看实现：
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
int n = pairs.size();
vector<int> dp(n, 1); // dp[i]表示以i结尾的所有子数链中，最大的子数链长度
// 先排个序，比较元素如果是vector的话，默认比较其第一个元素
// 刚刚好符合我们的需要，也就是v1[0] < v2[0]
sort(pairs.begin(), pairs.end());
int ret = 1;
for(int i = 1; i < n; ++i)
{
for(int j = i - 1; j >= 0; --j)
{
if(pairs[i][0] > pairs[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};5、最长定差子序列（medium）
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1：
输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。示例 2：
输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。示例 3：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。提示：
1 <= arr.length <= 105-104 <= arr[i], difference <= 104
解题思路 -- 不优化会超时
这道题其实也是和最长递增子序列差不多的，但是这道题如果单单只是套一下那个模板来写而不做优化的话，在 leetcode 的一些非常长的测试用例之下是跑不过去，下面先讲大概思路，再进行优化！
首先是状态表示，还是和以前一样，这里不赘述，dp[i] 表示以 i 结尾的所有子序列中，最大定差子序列的长度。
接着就是状态转移方程，在不优化之前，基本和以前是一样的，同样分为两种情况：
- 子序列长度等于1：就是当前数值本身，此时的定差子序列长度为1
- 子序列长度大于1：我们需要遍历 i 前面的所有子序列情况，看看其加上 i 处元素是否还是构成定差子序列，是的话，则判断是否为更大的长度，更大的话更新，反之则不用；而不构成定差子序列的话，就无需处理了，也就是
dp[i] = max(dp[i], dp[j] + 1)- 而判断是否构成定差子序列，就是判断
arr[i] - arr[j] == difference，满足的话才使用上面的状态转移方程更新
- 而判断是否构成定差子序列，就是判断
初始化的话，整个数组初始化为 1 即可，即满足当前位置的最小长度，也不会影响其它位置。
返回值的话，就是返回途中出现的最大定差子序列的长度，所以要用变量记录途中最大长度，最后返回即可！
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
int n = arr.size();
vector<int> dp(n, 1);
int ret = 1;
for(int i = 1; i < n; ++i)
{
// 从后往前找最右边的那个满足等差difference的值
for(int j = i - 1; j >= 0; --j)
{
if(arr[j] == arr[i] - difference)
{
dp[i] = dp[j] + 1;
break; // 只需要找最右边那个，找到了直接退出
}
}
ret = max(ret, dp[i]);
}
return ret;
}
}; 但是这种写法，在这道题中是会超时的，因为本身这种写法就是一个 的时间复杂度，所以我们必须优化一下！
优化思路 -- 借助哈希表的O(1)查找速度
首先我们想一下，这道题其实有个限制范围，就是我们要找的就是满足与 arr[i] 定差的那个数为结尾的定差子序列，简单地说就是找 arr[i] - difference 这个数，但是问题是，i 下标前面可能有多个满足 arr[i] - difference 的数啊，是不是都得判断一遍更新最大值呢❓❓❓
答案肯定是不用，假设当前 arr[1]、arr[2]、arr[4] 都满足到 arr[i] 是等差子序列的要求，那么我们只需要选择 arr[4] 即可，因为越靠近后面，它中间可能又出现了长度的新增，比如说 arr[3] 满足到 arr[4] 是等差子序列的要求，此时 dp[4] 肯定要比 dp[1] 和 dp[2] 要大一个长度，所以我们只需要选择最后面这个满足的即可！
但是这样子效率也没提高多少啊，顶多是从后往前找到这个满足到 arr[i] 的定差序列，但是有可能还是一个 O(n^2) 的时间复杂度啊，所以此时我们就要换一种方法，采用哈希表来记录 i 前遇到的值！
我们可以让哈希表的键值对，key 存放的是 i 之前遍历过的值，value 存放的是 i 位置处的 dp 值。
这样子有什么好处呢❓❓❓
我们只需要遍历一遍数组，在遍历到 i 的时候，我们只需要在 hash 表查找时候有满足 arr[i] - difference 的值出现过即可，并且我们不需要去判断，因为 hash 表的一个函数特性，也就是 operator[] 如果没找到对应的值的话，会返回 0，相当于什么都没做，所以我们不需要去判断是否存在该值，当然要判断也是可以的。
也就是说，很简单，只需要 hash[arr[i]] = hash[arr[i] - difference] + 1 来更新哈希表即可，而在遍历途中用变量记录下最大值，最后返回这个最大值即可，具体看以下代码，最重要的是掌握整个思想：
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
// 创建哈希表，存放i前出现过的值与其和dp值
unordered_map<int, int> hash;
int ret = 1;
for(int i = 0; i < arr.size(); ++i)
{
// 如果hash[arr[i] - difference]不存在的话返回0，加上1就是不存在时的默认长度，很妙！
hash[arr[i]] = hash[arr[i] - difference] + 1;
ret = max(ret, hash[arr[i]]);
}
return ret;
}
};6、最长的斐波那契子序列的长度（medium）
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3- 对于所有
i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: arr = [1,2,3,4,5,6,7,8]
输出: 5
解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。示例 2：
输入: arr = [1,3,7,11,12,14,18]
输出: 3
解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。提示：
3 <= arr.length <= 10001 <= arr[i] < arr[i + 1] <= 10^9
解题思路
这道题比较难在状态表示，因为一维的 dp 表并不适合这道题，我们还是从一维 dp 表来切入，看看为什么不适合这道题。
首先根据 “经验 + 题目要求”，我们立马就能想到 dp[i] 表示以 i 结尾的所有斐波那契子序列中，最大的斐波那契子序列长度。
根据这个状态表示，推导状态转移方程的时候，结合题目要求说这个子序列起码得有三个元素构成，为了降低时间复杂度，我们可以给三个元素的后两个元素定位置，分别是下标 i 和 j，而第一个元素的下标我们设为 k，结合斐波那契的特点：arr[k] + arr[i] = arr[j]，可以很容易得到 arr[k] = arr[j] - arr[i]，也就是说我们只需要根据 i 和 j 位置的元素就能知道第一个元素应该是哪个值，并且结合哈希表，就能马上知道是否有存在这第一个元素，让时间复杂度降为 O(n^2)。
但是问题来了，我们先来推导一下状态转移方程：因为我们遍历的时候，只需要考虑 i 和 j，而 k 的元素是由它们两个位置的元素来得到的，此时就会出现这种情况：
- arr[k] 存在，且 k < i：
- 这种情况就是这个状态表示问题所在，因为我们找到了满足要求的 arr[k]，所以此时 dp[j] 要更新为新长度，也就是以 k 和 i 为结尾的斐波那契子序列的长度加上 arr[j]，也就是 dp[i] + 1，但是问题来了，你怎么确定 dp[i] 的最长斐波那契子序列的前一个元素是 k 呢❓❓❓
- 对不对，这是无法保证的，有可能在求 dp[i] 的时候，其以 i 结尾的最长斐波那契子序列的前一个元素并不是 k，这也就自然无法让 dp[j] = dp[i] + 1 得到保证，所以我们这种状态表示是错误的！
从上面的情况一就可以看出这种状态表示是不通的，因为我们并不知道 arr[k] 到底是不是以 i 结尾的最长斐波那契子序列中倒数第二个元素，所以我们必须把所有的情况都考虑，所以我们要用一个二维数组来表示状态。
也就是说，dp[i][j] 表示以 i 为倒数第二个元素，以 j 为结尾的所有子序列中，最长的斐波那契子序列的长度。
下面重新来推导一下状态转移方程，通过 k 处元素是否存在以及位置可以分为三种情况：
-
arr[k] 存在，且 k < i：
-
从下图可以推出，
dp[i][j] = dp[k][i] + 1，详细的参考图片思考！
-
-
arr[k] 存在，且 i <= k < j：
- 这种情况其实是不允许的，因为题目说过了，要求是严格递增子序列，而我们设定 i 和 j 的位置是这个子序列的最后两个元素，此时 k > i 的话就不符合了，所以还是 i 和 j 处两个元素自己玩，也就是 dp[i][j] = 2
-
arr[k] 不存在：
- 很明显这种情况就是找不到满足 arr[i] 和 arr[j] 的斐波那契子序列，两个元素只能自成一组了，也就是 dp[i][j] = 2
接着就是初始化问题，因为这道题给出的最短长度就是三个元素，我们也肯定是从 arr[2] 也就是第三个元素开始判断才有意义，那么就有可能出现前三个元素不满足斐波那契子序列的情况，此时我们给到第三个元素的值就是第二个元素和第三个元素自成一组的长度，也就是 2，所以我们初始化的时候把 dp 表初始化为 2 即可！
遍历顺序的问题，就是从上往下，而从右往左还是从左往右这个并不需要强制要求，因为从上往下最重要的就是控制 [k, i] 在 [i, j] 之前就遍历到！
返回值问题还是一样，有可能最大长度在途中存在，所以要用变量在遍历的时候保存最大值，但是最后我们不能随便的就返回这个最大值了，应该加一步判断，判断此时这个保存的最大值是否大于等于 3，因为题目要求如果不存在一个最长的斐波那契子序列的话，返回 0，否则才返回最大值。
优化
和上一道题一样，这道题我们的 k 处元素是通过后两个元素推导的，所以可以直接访问，但是想要判断是否存在，为了提高效率，我们可以使用哈希表来存储遍历过的那些值，记录下它们出现的值以及下标，就能快速定位到它们在数组中的位置！
具体的参考下面代码：
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size();
// 优化
// key：存放arr中元素的值
// value：存放元素值对应在arr中的下标
unordered_map<int, int> hash;
for(int i = 0; i < n; ++i)
hash[arr[i]] = i;
// 创建二维dp表，并且初始化所有元素为2
vector<vector<int>> dp(n, vector<int>(n, 2));
int ret = 2;
for(int j = 2; j < n; ++j) // 为了保持和题解的一致性，这里以j为最外层循环
{
// i从1开始，因为第一位置还要留给k
for(int i = 1; i < j; ++i)
{
int tmp = arr[j] - arr[i]; // 获取arr[k]的值
// 只有当arr[k]存在，并且下标小于i才进行更新
if(hash.count(tmp) && hash[tmp] < i)
{
dp[i][j] = dp[hash[tmp]][i] + 1;
ret = max(ret, dp[i][j]);
}
}
}
// 如果ret=2说明不存在最长的斐波那契子序列，则返回0
if(ret == 2)
return 0;
return ret;
}
};7、最长等差数列（medium）
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。提示：
2 <= nums.length <= 10000 <= nums[i] <= 500
解题思路 + 优化
这道题虽然说和上面的第五题有点像，但是其实更难一点，因为之前那道题的等差值是定值，而这道题就不一样了，这个等差值大小是不确定的，所以其实也可以浅浅的看出来之前的状态表示是不太行的，这里还是从以前的状态表示来切入，来分析分析。
状态表示还是和一起一样，“经验 + 题目要求”，所以可以得到 dp[i] 表示以 i 结尾的所有子序列中，最长的等差数列的长度。
这个时候我们来推一下状态转移方程，首先还是和上一道题一样，假设最后一个元素位置 i 和倒数第二个元素位置 j 是固定的，可以求出它们的等差值也就是 arr[i] - arr[j]，此时又可以顺势通过 arr[j] 和这个等差值来获取到前一个符合这个等差值的数，如下图所示：
此时在推导 dp[i] 的时候，其实就 相当于是以 j 结尾的最大等差数列也就是 dp[j] 加上一个 arr[i] 的长度，也就是加上一个单位长度，但是 问题就来了，怎么保证 dp[j] 也就是以 j 结尾的最大等差数列的等差值和此时的等差值是一样的呢❓❓❓
是的，无法保证，所以这种状态表示就是走不通的，我们 必须换一种状态表示！
出现上面这种情况的原因是因为我们没办法保证这个等差值一致的情况，所以这里我们的状态表示可以改为一个二维数组，dp[j][i] 表示以 j 为倒数第二个元素，以 i 为结尾的所有子序列中，最长的等差数列的长度。
这样子一来就行了，为什么呢❓❓❓
因为其实 dp[j][i] 和 dp[i] 确实没两样，但是最重要的是之前我们想表示的 dp[j] 就能固定住等差值了，假设我们推出的等差值，通过 arr[j] 能找到倒数第三个元素 arr[k]，并且 k < j，此时 dp[k][j] 之间的等差值表示就和 dp[j][i] 是一样的，就是刚才得到的等差值所以我们就能顺利推出状态转移方程！
推导状态转移方程的时候，根据 arr[k] 是否存在与位置分布，可以分为三种情况：
-
arr[k] 不存在：
- 此时只有 arr[j] 和 arr[i] 两个元素构成等差数列，所以长度为 2
-
arr[k] 存在，且 j <= k <= i
- 因为我们固定了 j 和 i 的位置分别是这个等差数列的倒数第二个元素和最后一个元素，所以如果出现 k 下标落在 j 和 i 之间，那么是不允许的，此时也是只有 arr[j] 和 arr[i] 两个元素构成等差数列，所以长度为 2
-
arr[k] 存在，且 k < j
-
此时说明 arr[k] 肯定是符合这个等差值的要求，但是问题是有可能有多个符合这个等差值比如下图中的 arr[k1] 和 arr[k2]，此时我们只需要选择 arr[k2]，也就是选择靠近 arr[j] 的那个 arr[k]，为什么呢❓❓❓
-
因为越放到后面的元素，可能因为 k1 和 k2 之间存在很多元素，而它们之间也有符合与 arr[k2] 满足等差序列的元素，那么此时 dp[k2] 肯定是大于等于 dp[k1] 的，所以我们题目要求选择最长的，那么肯定只需要选择最长的那个即可，并且 k2 中符合等差序列的情况肯定也包括了 k1 那种情况，这个是很容易想到的！
-
所以结合图片的解析，可以推出
dp[j][i] = dp[k2][j] + 1
-
接下来我们先讲一下优化的问题，因为和前两道题一样，arr[k] 是通过 arr[j] 和 arr[i] 来推导的，但是如果写代码的话我们还是得去遍历看看哪个 arr[k] 是符合等差值的，即使是寻找最后一个 arr[k] 从右往左找，也顶不住可能每次都找到最左端的情况，时间复杂度非常的高，所以我们要借助哈希表来存放这些遍历过的值，以便快速寻访！哈希表中映射的是数组中元素的值和其在数组中的下标！
那么就有一个问题，能不能像上一道题一样，在开始就将所有元素的值和下标映射到哈希表中呢❓❓❓
答案是不行的，因为有可能在 arr[i] 后面也存在符合等差的 arr[k]，上一道允许这么做的原因是因为上一道题是严格递增的，而这道题没有这个限制，所以我们只能边遍历边映射到哈希表！
初始化问题：因为结合题目要求，最小长度为 2，所以我们将所有元素初始化为 2 就行了！
💥💥💥遍历顺序问题：这个问题在这道题其实就是一个坑，非常的隐晦，我们之前在做题的时候，其实对遍历的顺序并不是很关注，但是这道题却变成了细节，通常我们会有两种遍历方式（下面的 j 和 i 是结合上面的解题出的，遵循 j < i 的规则）：
- 方式一：先固定最后一个数下标 i，枚举倒数第二个数下标 j
- 方式二：先固定倒数第二个数下标 j，枚举最后一个数下标 i
一般来说我们都会选择第一种遍历方式，但是这种遍历方式在这道题其实会有问题，虽然可以解决，但是效率会变低，因为我们需要用到哈希表来存放遍历过的值，但是问题是遍历方式一中，倒数第二个数在枚举的时候，会不断的回到最左边的元素再重新从左往右遍历，此时如果数组中有重复的值并且 j 之前已经遍历过多个重复的这些值，那么哈希表中这个重复的值是最右边的那个，但是 i 更新之后，重新枚举 j 的时候，此时如果只遍历到了第一个重复的值，并不需要考虑到更右边的值，但是哈希表中存放的重复的那个值下标是更右边的那个值，这样子就导致了错误！
要解决这个问题也不难，只需要当 j 重新遍历的时候重新映射哈希表即可，当时没必要，这样子反而麻烦了！
所以采用遍历方式二，因为 j 是先固定的，我们只将 i 向后枚举，所以每次 i 走到底了之后， j 往后走，所以不会出现 j 重新从左往右的情况，就避免了这种问题！
返回值问题：因为最大长度可能是在途中产生的，所以要用变量记录下来。因为最短的数组长度是 2，所以 j 是从下标 0 开始遍历（不需要考虑 k，因为找不到也没关系），而 i 肯定是从下标 1 开始遍历，如果数组长度为 2，那么就不会进入循环体了，最后返回的就是也应该是 2，所以我们的变量初始化的时候，要初始化为 2，保证最后返回的正确性！
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 2)); // 创建dp表，并都初始化为2
unordered_map<int, int> hash; // 创建哈希表，存放nums元素值和其对应的下标
// 将第一个元素映射到哈希表中
hash[nums[0]] = 0;
int ret = 2;
// 遍历方式1：固定最后一个元素下标i，移动倒数第二个元素下标j
// 遍历方式2：固定倒数第二个元素下标j，移动最后一个元素下标i
// 这里方式1是错误的，要选择方式2，因为方式1中倒数第二个元素下标一直在变，而哈希表中重复元素放的值是最右边的那个值，没办法保证j重新从左往右遍历的时候哈希表中的值的范围还在j之前，这样子又得重新映射一遍遍历的值
for(int j = 1; j < n - 1; ++j) // 固定倒数第二个元素下标
{
for(int i = j + 1; i < n; ++i) // 移动最后一个元素下标
{
int tmp = 2*nums[j] - nums[i]; // 算出arr[k]的值，因为差值为nums[i]-nums[j]
if(hash.count(tmp))
{
// 只有当符合等差的那个数值存在才进行更新
dp[j][i] = dp[hash[tmp]][j] + 1;
ret = max(ret, dp[j][i]);
}
}
// 映射当前数值和下标到哈希表，并且这样子保证了如果出现相同元素，那么最新的映射一定是最后面那个数值
hash[nums[j]] = j;
}
return ret;
}
};8、等差数列划分II - 子序列（hard）
给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。
如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
- 例如，
[1, 3, 5, 7, 9]、[7, 7, 7, 7]和[3, -1, -5, -9]都是等差序列。 - 再例如，
[1, 1, 2, 5, 7]不是等差序列。
数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。
- 例如，
[2,5,10]是[1,2,1,2,4,1,5,10]的一个子序列。
题目数据保证答案是一个 32-bit 整数。
示例 1：
输入：nums = [2,4,6,8,10]
输出：7
解释：所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]示例 2：
输入：nums = [7,7,7,7,7]
输出：16
解释：数组中的任意子序列都是等差子序列。提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1
解题思路 + 哈希表优化
首先是状态表示，根据 “经验 + 题目要求“，我们可以定义 dp[i] 表示以 i 结尾的所有子序列中，等差数列出现的个数。
在推导状态转移方程的时候，会发现这个状态表示其实不对，因为如果我们用两层循环，遍历 i 和 j，此时算出它们元素之间的差值 tmp，那么 dp[i] 就一定会等于 dp[j] + 1 吗，答案肯定不是，因为 dp[j] 是以 j 结尾的所有子序列中等差数列出现的个数，但是我们并不知道，这些子序列中它们自己的等差值具体是多少，不一定是等于 tmp 的，所以这个状态表示明显是不行的！
所以我们要重新定义一下状态表示，其实和前几道题有点类似，既然我们已经知道了 i 和 j 元素之间的差值了，但是不知道 j 的子序列中的元素与 j 之间的差值，为了建立关系，这里我们就要固定两个元素位置，相当于以 j 为中轴联系起来前后关系！
所以状态表示定义为 dp[j][i] 表示以 j 为倒数第二个元素，以 i 结尾的所有子序列中，等差数列出现的个数！
再来重新推导一下状态转移方程，因为我们固定了后两个元素，分别是 j 和 i 处的元素，那么根据等差数列的性质，我们可以得到 j 之前的那个符合等差值的元素，假设它的下标为 k，那么 nums[k] = 2*nums[j] - nums[i]，所以我们只需要两层 for 循环来遍历 j 和 i，然后通过公式来判断是否存在 nums[k]，并且要求 k < j，这是我们人为规定的！
回到正题，既然求的是 dp[j][i]，也就是以 j 为倒数第二个元素，以 i 结尾的所有子序列中等差数列的个数，其实就转变为求 dp[k][j]，也就是以 k 为倒数第二个元素，以 j 为结尾的所有子序列中等差数列的个数，再加上当前的 nums[i] 元素！
但是和之前不太一样的是，这道题求的是个数，所以如果 nums[k] 是存在的话，那么 [k, j, i] 三个元素本身也构成了一个等差数列，再加上 dp[k][j]，其实就能得到 dp[j][i] = dp[k][j] + 1。
还没结束，因为在 j 之前 nums[k] 可能存在多个，之前的题目都是取最后一个 nums[k]，是因为要求最大长度，但是这道题要求的是次数，所以我们必须所有的 nums[k] 都考虑上，也就是说 dp[j][i] 必须累加上每个 nums[k] 序列的可能，最后得到状态转移方程 dp[j][i] += dp[k][j] + 1。
优化问题：因为有可能 nums[k] 有多个的原因，如果我们直接再加一层循环的话，那么时间复杂度就达到 O(n^3) 了，那可不行，所以要适当的优化一下，思路还是使用哈希表，和之前不太一样的是，现在哈希表中虽然也是要装载 <元素值，下标>，但是会发现因为有重复的元素，下标会被不断更新，为了防止这种情况，我们的 value 值用数组来装载这些下标，也就是 <元素值，下标数组> 的形式的哈希表。
然后只需要求出 nums[k] 之后通过哈希表判断是否存在 nums[k]，存在的话才去遍历这个下标数组去累加每个 nums[k] 序列的次数，并且只需要遍历 j 下标之前的 nums[k]，因为我们人为规定 k < j，也就是 j 一定要是倒数第二个元素下标！
遍历问题：这道题对遍历顺序不太讲究，先固定 i 和 j 哪个都行！
初始化问题：因为这道题求的是长度，并且要求三个元素以上的子序列才能构成等差数列，所以我们没必要从前两个元素开始遍历，所以全部元素都初始化为 0 即可！
返回值问题：因为这道题要的是全部的等差数列的个数，所以我们当求完每个 dp[j][i] 之后就可以用变量来累加出现的个数！
💥💥💥这道题的坑还有一个，因为数值范围比较大，在求 nums[k] 的时候，用到 2*nums[j]，这可能会溢出 int 类型的范围，所以我们要先转化为 long long 类型，这样子才能保证数据正确！
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// 哈希表优化，防止溢出，用长整型
unordered_map<long long, vector<int>> hash;
for(int i = 0; i < n; ++i)
hash[nums[i]].push_back(i);
int ret = 0;
for(int i = 2; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
long long tmp = (long long)2*nums[j] - nums[i]; // 防止溢出，用长整型
if(hash.count(tmp))
{
// 遍历tmp的下标数组
for(auto k : hash[tmp])
{
if(k >= j) // 如果大于当前的j下标，则直接break
break;
dp[j][i] += dp[k][j] + 1;
}
}
ret += dp[j][i]; // 累加出现次数
}
}
return ret;
}
};