目录
①力扣300. 最长递增子序列
难度 中等
给你一个整数数组 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-10^4 <= nums[i] <= 10^4
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
}
};解析代码
以某个位置为结尾，结合题目要求，定义一个状态表示： dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度。
状态转移方程： 对于 dp[i] ，我们可以根据子序列的构成方式，进行分类讨论：
- 子序列长度为 1 ：此时 dp[i] = 1 ;（可以把dp表全初始化成1）
- 子序列长度大于 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] 。
从左往右填表，最后返回dp表的最大值即可。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
// dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度
int n = nums.size(), ret = 1;
vector<int> dp(n, 1);
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[j] < nums[i])
dp[i] = max(dp[j] + 1, dp[i]);
}
ret = max(dp[i], ret);
}
return ret;
}
};②力扣376. 摆动序列
难度 中等
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
-
例如，
[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
进阶：你能否用 O(n) 时间复杂度完成此题?
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
}
};解析代码
以某个位置为结尾，结合题目要求，定义一状态表示： dp[i] 表示：以 i 位置为结尾的最长摆动序列的长度。
但是问题来了，如果状态表示这样定义的话，以 i 位置为结尾的最长摆动序列的长度没法从之前的状态推导出来。因为我们不知道前一个最长摆动序列的结尾处是递增的，还是递减的。因此，还需要状态表示能表示多⼀点的信息：要能让我们知道这⼀个最⻓摆动序列的结尾是递增的还是递减的。解决的方式很简单：开两个 dp 表。
- f[i] 表示：以 i 位置元素为结尾的所有的子序列中，最后一个位置呈现上升趋势的最长摆动序列的长度。
- g[i] 表示：以 i 位置元素为结尾的所有的子序列中，最后一个位置呈现下降趋势的最长摆动序列的长度。
由于子序列的构成比较特殊， i 位置为结尾的子序列，前一个位置可以是 [0, i - 1] 的任意位置，因此设 j 为 [0, i - 1] 区间内的某一个位置。
对于 f[i] ，可以根据子序列的构成方方式，进行分类讨论：
- 子序列长度为 1 ：此时 f[i] = 1; （可以把dp表全初始化成1）
- 子序列长度大于 1 ：因为结尾要呈现上升趋势，因此需要 nums[j] < nums[i] 。在满足这个条件下， j 结尾需要呈现下降状态，最长的摆动序列就是 g[j] + 1 。因此我们要找出所有满足条件下的最大的 g[j] + 1 。
综上， f[i] = max(g[j] + 1, f[i]) ，使用 g[j] 时需要判断。
对于 g[i] ，也可以根据子序列的构成方方式，进行分类讨论：
- 子序列长度为 1 ：此时 f[i] = 1; （可以把dp表全初始化成1）
- 子序列长度大于 1 ：因为结尾要呈现下降趋势，因此需要 nums[j] > nums[i] 。在满足这个条件下， j 结尾需要呈现上升状态，因此最长的摆动序列就是 f[j] + 1 。 因此要找出所有满足条件下的最⼤的 f[j] + 1 。
综上， g[i] = max(f[j] + 1, g[i]) ，使用 f[j] 时需要判断。
从左往右填表，最后返回两个表中的最大值。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size(), ret = 1;
vector<int> f(n, 1), g(n, 1);
//以i位置元素为结尾的子序列，最后一个位置呈现上升/下降趋势的最长摆动序列的长度
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[j] < nums[i])
f[i] = max(g[j] + 1, f[i]);
else if(nums[j] > nums[i])
g[i] = max(f[j] + 1, g[i]);
}
ret = max(ret, max(f[i], g[i]));
}
return ret;
}
};③力扣673. 最长递增子序列的个数
难度 中等
给定一个未排序的整数数组 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-10^6 <= nums[i] <= 10^6
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
}
};解析代码
尝试定义一个状态：以 i 为结尾的最长递增子序列的「个数」。那么问题就来了，我都不知道 以 i 为结尾的最长递增子序列的长度是多少，我怎么知道最长递增子序列的个数呢？ 因此解决这个问题需要两个状态，一个是长度，一个是个数：
- len[i] 表示：以 i 为结尾的最长递增子序列的长度。
- count[i] 表示：以 i 为结尾的最长递增子序列的个数。
状态转移方程： 求个数之前得先知道长度，因此先看 len[i] ：
在求 i 结尾的最长递增序列的长度时，我们已经知道 [0, i - 1] 区间上的 len[j] 信息，用 j 表示 [0, i - 1] 区间上的下标。
我们需要的是递增序列，因此 [0, i - 1] 区间上的 nums[j] 只要能和 nums[i] 构成上升序列，那么就可以更新 dp[i] 的值，此时最长长度为 dp[j] + 1 ;
我们要的是 [0, i - 1] 区间上所有情况下的最大值。 综上所述，对于 len[i] ，我们可以得到状态转移方程为： len[i] = max(len[j] + 1, len[i]) ，其中 0 <= j < i ，并且 nums[j] < nums[i] 。
在知道每一个位置结尾的最长递增子序列的长度时，来看看能否得到 count[i] ：
此时已经知道 len[i] 的信息，还知道 [0, i - 1] 区间上的 count[j] 信 息，用 j 表示 [0, i - 1] 区间上的下标。可以再遍历一遍 [0, i - 1] 区间上的所有元素，只要能够构成上升序列，并且上升序列的长度等于 dp[i] ，那么就把 count[i] 加上 count[j] 的值。这样循环一遍之后， count[i] 存的就是我们想要的值。
综上所述，对于 count[i] ，我们可以得到状态转移方程为： count[i] += count[j] ，其中 0 <= j < i ，并且 nums[j] < nums[i] && len[j] + 1 == len[i] 。
如果len[j] + 1 > len[i]，len[i] = len[j] + 1，count[i] = count[j]。
初始化、填表顺序、返回值：
对于 len[i] 和count[i] ，所有元素自己就能构成一个上升序列，直接全部初始化为 1。
从左往右填表，最后返回len表最大的元素的最大个数。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> len(n, 1), count(n, 1);
// len[i] 表示：以 i 为结尾的最长递增子序列的长度。
// count[i] 表示：以 i 为结尾的最长递增子序列的个数。
int retLen = 1, retCount = 1; // 记录最终结果
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[j] < nums[i]) // 是递增序列
{
if(len[j] + 1 == len[i]) // 长度一样，加等个数
count[i] += count[j];
else if(len[j] + 1 > len[i]) // 最长长度换了，重新计数
len[i] = len[j] + 1, count[i] = count[j];
}
}
if(retLen == len[i]) // 长度一样，加等个数
retCount += count[i];
else if(retLen < len[i]) // 最长长度换了，重新计数
retLen = len[i], retCount = count[i];
}
return retCount;
}
};④力扣646. 最长数对链
难度 中等
给你一个由 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
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
}
};解析代码
这道题目让我们在数对数组中挑选出来⼀些数对，组成⼀个呈现上升形态的最长的数对链。像不像整数数组中挑选一些数，让这些数组成⼀个最长的上升序列？因此，我们可以把问题转化成我 们学过的一个模型： 力扣300. 最长递增子序列。因此我们解决问题的方向在此模型上。 不过，与整形数组有所区别。在用动态规划结局问题之前，应该先把数组排序。因为我们在计算 dp[i] 的时候，要知道所有左区间比 pairs[i] 的左区间小的链对。排完序之后，只用往前遍历一遍即可。
状态表示： dp[i] 表示以 i 位置的数对为结尾时，最长数对链的长度。
状态转移方程： 对于 dp[i] ，遍历所有 [0, i - 1] 区间内数对用 j 表示下标，找出所有满足 pairs[j] [1] < pairs[i][0] 的 j 。找出里面最大的 dp[j] ，然后加上 1 ，就是以 i 位置为结尾的最长数对链。
dp表全初始化成1，从左往右填表，最后返回dp表的最大值即可。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end());
int n = pairs.size(), ret = 1;
// dp[i] 表示以 i 位置的数对为结尾时，最长数对链的长度
vector<int> dp(n, 1);
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(pairs[j][1] < pairs[i][0])
dp[i] = max(dp[j] + 1, dp[i]);
}
ret = max(ret, dp[i]);
}
return ret;
}
};⑤力扣1218. 最长定差子序列
难度 中等
给你一个整数数组 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 <= 10^5-10^4 <= arr[i], difference <= 10^4
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
}
};解析代码
这道题和 力扣300. 最长递增子序列有⼀些相似，但仔细读题就会发现，本题的 arr.lenght 高达10^5 ，使用 O(N^2) 的 lcs 模型⼀定会超时。
那么它有什么信息是力扣300. 最长递增子序列的呢？是定差。之前只知道要递增，不知道前一个数应当是多少，现在我们可以计算出前一个数是多少了，就可以用数值来定义 dp 数组的值，并形成状态转移。这样，就把已有信息有效地利用了起来。
状态表示：dp[i] 表示：以 i 位置的元素为结尾所有的子序列中，最长的等差子序列的长度。
状态转移方程：对于 dp[i] ，上一个定差子序列的取值定为 arr[i] - difference 。只要找到以上一个数字为结尾的定差子序列长度的 dp[arr[i] - difference] ，然后加上 1 ，就是以 i 为结尾的定差子序列的长度。 因此这里可以选择使用哈希表做优化。把元素和dp[j] 绑定，放进哈希表中。甚至不用创建 dp 数组，直接在哈希表中做动态规划。
初始化、填表顺序、返回值：
刚开始的时候，需要把第一个元素放进哈希表中， hash[arr[0]] = 1 。
从左往右填表，最后返回dp表的最大值即可。
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
// dp[i] 表示：以 i 位置的元素为结尾所有的子序列中，最长的等差子序列的长度。
int n = arr.size(), ret = 1;
unordered_map<int, int> dpHash(n);
dpHash[arr[0]] = 1;
for(int i = 1; i < n; ++i)
{
// if(dpHash[arr[i] - difference]) // b存在
// dpHash[arr[i]] = dpHash[arr[i] - difference] + 1;
// else
// dpHash[arr[i]] = 1;
dpHash[arr[i]] = dpHash[arr[i] - difference] + 1; // 不存在就是0，直接加
ret = max(ret, dpHash[arr[i]]);
}
return ret;
}
};⑥力扣873. 最长的斐波那契子序列的长度
难度 中等
如果序列 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 <= 1000-
1 <= arr[i] < arr[i + 1] <= 10^9
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
}
};解析代码
动态规划解法思路：
状态表示：以某个位置为结尾，结合题目要求，先定义⼀个状态表示：
dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长的斐波那契子数列的长度。
但是这里有⼀个非常致命的问题，那就是我们无法确定 i 结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程，因此我们定义的状态表示需要能够确定一个斐波那契序列。
根据斐波那契数列的特性，我们仅需知道序列里面的最后两个元素，就可以确定这个序列的样子。因此，修改状态表示为：
dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度。规定一下 i < j 。
状态转移方程：
设 nums[i] = b, nums[j] = c ，那么这个序列的前一个元素就是 a = c - b 。根据 a 的情况讨论：
- a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的最长斐波那契子序列的长度，然后再加上 j 位置的元素（+1）即可。于是 dp[i][j] =dp[k][i] + 1 ;
- a 存在，但是 b < a < c ：此时只能有两个元素， dp[i][j] = 2 ;
- a 不存在：此时依旧只有两个元素， dp[i][j] = 2 ;
综上，状态转移方程分情况讨论即可。
优化点：我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将所有的元素和下标绑定在一起，放到哈希表中。
初始化：可以将表里面的值都初始化为 2 。
填表顺序：先固定斐波那契子序列的最后一个数，然后枚举倒数第二个数。
返回值：因为不知道最终结果以谁为结尾，因此返回 dp 表中的最大值 ret 。但是 ret 可能小于 3 ，小于 3 的话说明不存在。因此需要判断一下。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
int n = arr.size(), ret = 2;
unordered_map<int, int> hash(n);
for(int i = 0; i < n; ++i)
{
hash[arr[i]] = i;
}
vector<vector<int>> dp(n, vector<int>(n, 2));
// dp[i][j] 表示：以i位置及j位置的元素为结尾的子序列中，最长的斐波那契子序列的长度。i < j
for(int j = 2; j < n; ++j) // 斐波那契子数列最后一个位置
{
for(int i = 1; i < j; ++i) // 斐波那契子数列倒数第二个位置
{
int a = arr[j] - arr[i];
if(a < arr[i] && hash.count(a))
dp[i][j] = dp[hash[a]][i] + 1; // hash[a]就是a元素下标
ret = max(ret, dp[i][j]);
}
}
return ret < 3 ? 0 : ret;
}
};⑦力扣1027. 最长等差数列
难度 中等
给你一个整数数组 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
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
}
};解析代码
和力扣873. 最长的斐波那契子序列的长度类似，动态规划解法思路：
状态表示：以某个位置为结尾，结合题目要求，先定义⼀个状态表示：
dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长等差数列的长度。
但是这里有⼀个非常致命的问题，那就是我们无法确定 i 结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程，因此我们定义的状态表示需要能够确定一个等差数列
根据等差数列的特性，我们仅需知道序列里面的最后两个元素，就可以确定这个序列的样子。因此，修改状态表示为：
dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的等差数列的长度。规定⼀下 i < j 。
状态转移方程：
设 nums[i] = b, nums[j] = c ，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
- a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的等差数列的长度，然后再加上 j 位置的元素（+1）即可。于是 dp[i][j] =dp[k][i] + 1 ;
- a 存在，但是 b < a < c ：此时只能有两个元素， dp[i][j] = 2 ;
- a 不存在：此时依旧只有两个元素， dp[i][j] = 2 ;
综上，状态转移方程分情况讨论即可。
优化点：我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将所有的元素和下标绑定在一起，放到哈希表中。这样时间复杂度较高，会超时。
能否一边 dp ，一边保存？这种方式，我们仅需保存最近的元素的下标，不用保存下标数组。但是用这种方法的话，在填表顺序那里，先固定倒数第二个数，再遍历倒数第一个数。这样就可以在 i 使用完时候，将 nums[i] 扔到哈希表中。
初始化：可以将表里面的值都初始化为 2 。
填表顺序：先固定最长的等差数列的倒数第二个数，再遍历倒数第⼀个数。
返回值：返回 dp 表中的最大值。（有2也返回2，题目没有力扣873严谨）
class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size(), ret = 2;
vector<vector<int>> dp(n, vector<int>(n, 2));
// dp[i] 表示：以 i 位置元素为结尾的所有子序列中，最长等差数列的长度
unordered_map<int, int> hash(n);
hash[nums[0]] = 0;
for(int i = 1; i < n; ++i) // 先固定倒数第二个数
{
for(int j = i + 1; j < n; ++j) // 固定倒数第一个数
{
int a = 2 * nums[i] - nums[j];
if(hash.count(a))
dp[i][j] = dp[hash[a]][i] + 1;
ret = max(ret, dp[i][j]);
}
hash[nums[i]] = i;
}
return ret;
}
};⑧力扣446. 等差数列划分 II - 子序列
难度 困难
给你一个整数数组 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-2^31 <= nums[i] <= 2^31 - 1
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
}
};解析代码
和力扣873. 最长的斐波那契子序列的长度、力扣1027. 最长等差数列类似，动态规划解法思路：
状态表示：以某个位置为结尾，结合题目要求，先定义一个状态表示：
dp[i] 表示：以 i 位置元素为结尾的所有子序列中，等差数列的个数。
但是这里有一个非常致命的问题，那就是我们无法确定 i 结尾的斐波那契序列的样子。这样就会导致我们无法推导状态转移方程，因此我们定义的状态表示需要能够确定一个等差数列
根据等差数列的特性，我们仅需知道序列里面的最后两个元素，就可以确定这个序列的样子。因此，修改状态表示为：
dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，等差数列的个数。规定一下 i < j 。
状态转移方程：
设 nums[i] = b, nums[j] = c ，那么这个序列的前一个元素就是 a = 2 * b - c。根据 a 的情况讨论：
- a 存在，下标为 k ，并且 a < b ：此时我们需要以 k 位置以及 i 位置元素为结尾的等差数列的长度，然后再加上 j 位置的元素（+1）即可。于是 dp[i][j] =dp[k][i] + 1 ; 因为 a 可能有很多个，我们需要全部累加起来。p[i][j] +=dp[k][i] + 1 ;
- a 存在，但是 b < a < c ：dp[i][j] =0 ;
- a 不存在： dp[i][j] = 0 ;
综上，状态转移方程分情况讨论即可。
优化点：我们发现，在状态转移方程中，我们需要确定 a 元素的下标。因此我们可以在 dp 之前，将所有的元素和下标数组绑定在⼀起，放到哈希表中。这里为什么保存下标数组，是因为要统计个数，所有的下标都需要统计。
初始化：可以将表里面的值都初始化为 0 。
填表顺序：先固定斐波那契子序列的最后一个数，然后枚举倒数第二个数。
返回值：返回 dp 表中的所有值的和。
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size(), ret = 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
// dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，等差数列的个数。i < j
unordered_map<long long, vector<int>> hash(n);
for(int i = 0; i < n; ++i)
{
hash[nums[i]].push_back(i);
}
for(int j = 2; j < n; ++j) // 固定倒数第一个数
{
for(int i = 1; i < j; ++i) // 先固定倒数第二个数
{
long long a = (long long)2 * nums[i] - nums[j]; // 防溢出
if(hash.count(a))
{
for(auto& k : hash[a])
{
if(k < i)
dp[i][j] += dp[k][i] + 1;
else
break;
}
}
ret += dp[i][j];
}
}
return ret;
}
};本篇完。
下一篇是队列_宽搜bfs类型的OJ。
下下篇动态规划类型的是回文串dp类型的OJ。
标签：元素,nums,19,由易到难,Offer,int,序列,最长,dp From： https://blog.csdn.net/GRrtx/article/details/136604040