动态规划四——子序列系列

目录

题目一——300. 最长递增子序列 - 力扣（LeetCode）

题目二——376. 摆动序列 - 力扣（LeetCode）

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

题目四——646. 最长数对链 - 力扣（LeetCode）

题目五——1218. 最长定差子序列 - 力扣（LeetCode）

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

题目七——1027. 最长等差数列 - 力扣（LeetCode）

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

题目一——300. 最长递增子序列 - 力扣（LeetCode）

首先子序列不是子数组！！

子序列 是可以通过从另一个数组删除或不删除某些元素，但不更改其余元素的顺序得到的数组。

说白了就是按从左往右的顺序挑选元素，组成的新数组就是子序列。每个元素的相对顺序是保持不变的！！！ 

我们下面看一个例子：

原数组：[1, 2, 3, 4, 5]

可能的子序列：

• [1, 2, 3] （保留了前三个元素）
• [1, 3, 5] （跳过了第二个和第四个元素）
• [1, 2, 4, 5] （跳过了第三个元素）
• [5] （只保留了最后一个元素）
• [1, 2, 3, 4, 5] （没有删除任何元素）
• [] （空数组也是任何数组的子序列，表示删除所有元素）

有没有发现，子序列就是包含了子数组。所以子序列的问题是比子数组的题目难的！！

1.状态表示：

对于线性 dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：

• i. 以某个位置为结尾，巴拉巴拉；
• ii. 以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：

使用动态规划（DP）数组 dp，其中 dp[i] 表示以 nums[i] 结尾的所有递增子序列中的最长长度。

2.状态转移方程：

像这种子数组或者子序列的状态转移方程的推导，都是从如何构成子序列或者子数组来解决的！！

我们看dp[i] 表示以 nums[i] 结尾的所有递增子序列中的最长长度

那以nums[i]为结尾的子序列可以分为下面几类：

1. 单独一个元素组成子序列：
2. 和前面的元素一起组成子序列（比如说跟在nums[i-1]后面形成子序列，或者跟在nums[i-2]后面，再或者跟在nums[i-3]后面……跟在nums[0]都是可以的

所以我们很容易就能推导出下面这个状态转移方程

1. 单独一个元素组成子序列：dp[i]=1;
2. 和前面的元素一起组成子序列：这个时候我们不能随便乱填dp[i]，我们可以回去看一下状态表示：一定要是最长子序列的长度，所以我们完全可以定义一个变量 j 从0开始往n-1进行遍历，看看哪个的dp[j]最大，哪个的最大就让nums[i]跟在它后面。所以就是最大的dp[j] + 1

由于我们要找最长的，所以最终的状态转移方程：

if (nums[i] > nums[j]) {

        dp[i] = max(dp[i],dp[j] + 1);

}

注意：我们回到这个题目，题目说找一个严格递增的子序列，所谓严格递增，就是子序列里面各个元素不能存在相等的情况，只能是nums[i]>nums[j]。 

3.初始化：

初始化我们是将它初始化为最差的情况。

每个元素单独都能构成一个递增子序列，因此初始时，dp[i] 应该被设置为 1（对于所有 i）。

4.填表顺序：

由于我们需要用到前面的状态来计算当前状态，因此填表顺序应该是从左往右（即从小到大的索引）。

5.返回值：

最长递增子序列的长度就是 dp 数组中的最大值。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);

        int ret=1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i-1; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
                ret=max(ret,dp[i]);
            }
        }
        return ret;
    }
};

题目二——376. 摆动序列 - 力扣（LeetCode）

 这个题目很像多状态dp啊

1. 状态表⽰：

对于线性 dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：

• i. 以某个位置为结尾，巴拉巴拉；
• ii. 以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：

• dp[i] 表⽰「以 i 位置为结尾的最⻓摆动序列的⻓度」。

但是，问题来了，如果状态表⽰这样定义的话，以 i 位置为结尾的最⻓摆动序列的⻓度我们没法 从之前的状态推导出来。因为我们不知道前⼀个最⻓摆动序列的结尾处是递增的，还是递减的。因 此，我们需要状态表⽰能表⽰多⼀点的信息：要能让我们知道这⼀个最⻓摆动序列的结尾是递增的 还是递减的。

解决的⽅式很简单：搞两个 dp 表就好了。

1. f[i] 表⽰：以 i 位置元素为结尾的所有的⼦序列中，最后⼀个位置呈现「上升趋势」的最⻓摆 动序列的⻓度；
2. g[i] 表⽰：以 i 位置元素为结尾的所有的⼦序列中，最后⼀个位置呈现「下降趋势」的最⻓摆 动序列的⻓度。

2.状态转移方程

像这种子数组或者子序列的状态转移方程的推导，都是从如何构成子序列或者子数组来解决的！！

那以nums[i]为结尾的子序列可以分为下面几类：

1. 单独一个元素组成子序列：
2. 和前面的元素一起组成子序列（比如说跟在nums[i-1]后面形成子序列，或者跟在nums[i-2]后面，再或者跟在nums[i-3]后面……跟在nums[0]都是可以的

由于子序列的构成比较特殊，对于 f[i]（即以 i 位置为结尾的子序列），其前一个位置 j 可以是 [0, i - 1] 区间内的某一个位置。我们可以根据子序列的构成方式进行分类讨论：

1. 单独一个元素组成子序列：此时，只能由单个元素自身构成，因此 [0, i - 1] 的任意 f[i] 初始化为 1。

2. 和前面的元素一起组成子序列：因为结尾要呈现上升趋势，所以需要 nums[j] < nums[i]。在满足这个条件下，j 结尾的子序列需要呈现下降状态，因此最长的摆动序列就是 g[j] + 1。我们需要找出所有满足条件下的最大 g[j] + 1，并更新 f[i]。

综上，对于 f[i] 的更新公式为：

f[i] = max(g[j] + 1, f[i])，其中 j 满足 0 <= j < i 且 nums[j] < nums[i]。

同理，对于 g[i]（即以 i 位置为结尾的子序列），我们也可以进行分类讨论：

1. 单独一个元素组成子序列：此时，只能由单个元素自身构成，因此 g[i] 初始化为 1。

2. 和前面的元素一起组成子序列：因为结尾要呈现下降趋势，所以需要 nums[j] > nums[i]。在满足这个条件下，j 结尾的子序列需要呈现上升状态，因此最长的摆动序列就是 f[j] + 1。我们需要找出所有满足条件下的最大 f[j] + 1，并更新 g[i]。

综上，对于 g[i] 的更新公式为：

g[i] = max(f[j] + 1, g[i])，其中 j 满足 0 <= j < i 且 nums[j] > nums[i]。

3.初始化：

由于每个元素单独都能构成一个摆动序列（长度为 1），因此我们可以将 f 和 g 两个 DP 表内的所有元素初始化为 1。

4.填表顺序：

毫无疑问，我们应该从左往右依次填充 DP 表，即按照数组 nums 的顺序进行。

5.返回值：

最终，我们应该返回两个 DP 表里面的最大值，这代表了最长的上升摆动子序列和下降摆动子序列中的最长者。我们可以在填表的过程中，顺便更新一个全局的最大值变量来记录这个结果。

所以我们很容易就想到下面这个代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        vector<int>f(n,1);
        vector<int>g(n,1);

        int ret=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=i-1;j++)
            {
                if(nums[j]<nums[i])
                {
                    f[i]=max(f[i],g[j]+1);
                }
                else if(nums[j]>nums[i])
                {
                    g[i]=max(g[i],f[j]+1);
                }
            }
            ret=max(ret,max(g[i],f[i]));
        }
        return ret;
    }
};

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

1.状态表示

对于线性 dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：

• i. 以某个位置为结尾，巴拉巴拉；
• ii. 以某个位置为起点，巴拉巴拉。

这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰：以 nums[i] 为结尾的最⻓递增⼦序列的「个数」。

那么问题就来了，我都不知道 以 i 为结尾的最⻓递增⼦序列的「⻓度」是多少，我怎么知道最⻓递增⼦序列的个数呢？

因此，我们解决这个问题需要两个状态，⼀个是「⻓度」，⼀个是「个数」：

• len[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的⻓度；
• count[i] 表⽰：以 i 为结尾的最⻓递增⼦序列的个数。

2.推导状态转移方程

这个时候我们讲一个小知识点。

  我们可以先讲一个小知识：

• 如何在数组中寻找最大值出现的个数？

有人可能说另外使用一个for循环，但是我们能不能只遍历一次就能解决问题呢？显然是可以的。

我们这里使用的是贪心的策略，我们使用一个maxval来标记最大值，然后使用一个count来计算最大值出现的次数.

接着我们从左往右扫描数组，会遇到下面3个情况

1. x==maxval：此时将count++；但是有人可能就说，当前这个数不是最大值啊？但是没关系，我们接着往下看。
2. x<maxval：直接无视
3. x>maxval：之前的统计废除，然后maxval=x；然后重新开始计数，即让count=1。

为了方便大家理解，我这里提供了一段代码

#include <iostream>
#include<vector>
using namespace std;


int main() {
    vector<int>nums = { 7,2,7,9,8,1,1,2,9,0,6,9,1 };
    int maxval = nums[0], count = 1;

    for (int i = 1; i < nums.size(); i++)
    {
        if (nums[i] == maxval)
        {
            count++;
        }
        else if (nums[i] > maxval)
        {
            maxval = nums[i];
            count = 1;
        }
    }
    cout <<"maxval:"<<maxval<<",count:"<< count << endl;
}

 像这种子数组或者子序列的状态转移方程的推导，都是从如何构成子序列或者子数组来解决的！！

那以nums[i]为结尾的子序列可以分为下面几类：

1. 单独一个元素组成子序列：
2. 和前面的元素一起组成子序列（比如说跟在nums[i-1]后面形成子序列，或者跟在nums[i-2]后面，再或者跟在nums[i-3]后面……跟在nums[0]都是可以的

 我们这里是要找最长的子序列的长度，也要找最长子序列的个数？

这和上面我们找最大的数，以及最大数的个数的思想是不是一模一样的啊？

所以我们完全可以len[i]和count[i]一起填。那怎么做呢？

首先len[i]=count[i]=1;  代表1个元素也能构成最长递增子序列，然后我们遍历原数组的[0,i-1]，然后符合nums[i]>nums[j]的，现在就会遇到3种情况

1. len[j]+1==len[i]：count[i]=count[j]；
2. len[j]+1<len[i]：不做处理
3. len[j]+1>len[i]：我们让len[i]=len[j]+1，之前统计的count[i]都作废，重新计数，即count[i]=count[j];

3.初始化：

◦ 对于 len[i] ，所有元素⾃⼰就能构成⼀个上升序列，直接全部初始化为 1 ； ◦ 对于 count[i] ，如果全部初始化为 1 ，在累加的时候可能会把「不是最⼤⻓度的情况」累 加进去，因此，我们可以先初始化为 0 ，然后在累加的时候判断⼀下即可。具体操作情况看代 码~

4.填表顺序：

毫⽆疑问是「从左往右」。

5.返回值：

⽤ maxLen 表⽰最终的最⻓递增⼦序列的⻓度。 根据题⽬要求，我们应该返回所有⻓度等于 maxLen 的⼦序列的个数。这个时候策略还是使用上面那个

我们很快就能写出这个代码 

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(); // 获取数组的大小
        vector<int> len(n, 1); // 用于存储以每个元素为结尾的最长递增子序列的长度，初始化为1
        vector<int> count(n, 1); // 用于存储以每个元素为结尾的、具有相同长度的最长递增子序列的个数，初始化为1

        int retlen = 1, retcount = 1; // 记录最终的最长递增子序列的长度和个数
        
        // 遍历数组中的每个元素
        for (int i = 1; i < n; i++) {
            // 对于每个元素nums[i]，检查它之前的所有元素
            for (int j = 0; j < i; j++) {
                // 如果nums[j]小于nums[i]，说明可以将nums[i]添加到以nums[j]为结尾的递增子序列中
                if (nums[j] < nums[i]) {
                    // 如果以nums[j]为结尾的子序列长度加1等于以nums[i]为结尾的子序列长度
                    // 则说明找到了一个新的、同样长的递增子序列，因此增加计数器count[i]
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } 
                    // 如果以nums[j]为结尾的子序列长度加1大于以nums[i]为结尾的子序列长度
                    // 则更新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. 最长数对链 - 力扣（LeetCode）

嗯？这题看起来和那个题目一差不多。

这道题⽬让我们在数对数组中挑选出来⼀些数对，组成⼀个呈现上升形态的最⻓的数对链。像不像 我们整数数组中挑选⼀些数，让这些数组成⼀个最⻓的上升序列？

因此，我们可以把问题转化成我 们学过的⼀个模型：题目一的。

因此我们解决问题的⽅向，应该在「最⻓递增⼦序 列」这个模型上。

不过，与整形数组有所区别。在⽤动态规划结局问题之前，应该先把数组排个序。因为我们在计 算dp[i] 的时候，要知道所有左区间⽐pairs[i] 的左区间⼩的链对。排完序之后，只⽤ 「往前遍历⼀遍」即可。

1.状态表示：

dp[i] 表示以第 i 个数对为结尾时，最长数对链的长度。

2.状态转移方程：

像这种子数组或者子序列的状态转移方程的推导，都是从如何构成子序列或者子数组来解决的！！

那以nums[i]为结尾的子序列可以分为下面几类：

1. 单独一个元素组成子序列：
2. 和前面的元素一起组成子序列（比如说跟在nums[i-1]后面形成子序列，或者跟在nums[i-2]后面，再或者跟在nums[i-3]后面……跟在nums[0]都是可以的

所以我们很容易就得到下面这个

1. 单独一个元素组成子序列：此时dp[i]=1
2. 和前面的元素一起组成子序列：对于 dp[i]，我们需要遍历 [0, i - 1] 区间内的所有数对（用 j 表示下标），并找出所有满足 pairs[j][1] < pairs[i][0] 的数对（也就是题目要求的b < c）。这是因为我们希望找到一个数对链，使得链中的每个数对的第二个元素都小于下一个数对的第一个元素，从而形成上升形态。

3. 在满足上述条件的数对中，我们需要找到 dp[j] 的最大值，并将其加1后赋给 dp[i]，即 dp[i] = max(dp[i],dp[j] + 1)（其中 j 满足 pairs[j][1] < pairs[i][0]）。

3.初始化：

在开始时，我们将 dp 数组的所有元素初始化为 1，因为每个数对单独都可以看作是一个长度为 1 的数对链。

4.填表顺序：

根据状态转移方程，我们需要按照从左到右的顺序来填充 dp 表。这是因为我们需要基于已经计算出的 dp[j]（j < i）来更新 dp[i]。

5.返回值：

根据状态表示，我们需要返回 dp 表中的最大值，这个值表示了最长上升数对链的长度。

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end());
        int n=pairs.size();
        vector<int>dp(n,1);

        int ret=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(pairs[i][0]>pairs[j][1])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            ret=max(dp[i],ret);
        }
        return ret;
    }
};

题目五——1218. 最长定差子序列 - 力扣（LeetCode）

有人的鼻子很敏锐啊，这不是类似于题目一吗？

它们很快就写出了下面这个代码

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++)
        {
            for(int j=0;j<i;j++)
            {
                if(arr[i]-arr[j]==difference)
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            ret=max(ret,dp[i]);
        }
        return ret;
    }
};

这是因为 

• 1 <= arr.length <= 105
• -104 <= arr[i], difference <= 104

数据很大啊！！！

那么，它有什么信息是300.最⻓递增⼦序列的呢？是定差。

之前，我们只知道要递增，不知道前 ⼀个数应当是多少；现在我们可以计算出前⼀个数是多少了，就可以⽤数值来定义 dp 数组的 值，并形成状态转移。这样，就把已有信息有效地利⽤了起来。

所以我们需要进行优化：

for(int j=0;j<i;j++)：这个过程是一个一个往前面遍历寻找前面一个符合arr[i]-arr[j]==difference的，那我为什么不直接将元素+dp[j]的值放到哈希表里面？？就像hash{arr[i],dp[i]} ，这样子，就能直接通过hash[arr[i]-difference] 找到前面符合的hash[arr[j]]，然后直接就能在这个哈希表里面进行动态规划！！！！
 

1.状态表示：

dp[i]（在哈希表中表示为 hash[arr[i]]）表示以 arr[i] 结尾的所有子序列中，最长的等差子序列的长度。但在这里，我们不会显式地创建一个 dp 数组，而是使用哈希表 hash 来存储每个元素对应的最长等差子序列长度。

2.状态转移方程：

对于 dp[i]（即 hash[arr[i]]），我们需要找到上一个等差子序列的末尾元素 arr[j]（即 hash[arr[j]]），使得 arr[i] - arr[j] = difference，其中 difference 是等差子序列的公差。

一旦找到这样的 arr[j]，我们就可以通过 dp[j] + 1 （即 hash[arr[i]-difference]+1]）来更新 dp[i]（即 hash[arr[i]]），表示以 arr[i] 结尾的等差子序列的新长度。

为了优化查找过程，我们使用哈希表来存储每个元素及其对应的最长等差子序列长度。

3.初始化：

在开始时，我们需要将数组的第一个元素 arr[0] 放入哈希表中，并初始化其最长等差子序列长度为 1，即 hash[arr[0]] = 1。

4.填表顺序：

根据状态转移方程，我们需要从左到右遍历数组 arr，并依次更新哈希表中的值。

5.返回值：

遍历完整个数组后，我们需要遍历哈希表，找到其中的最大值，这个值就表示了最长的等差子序列的长度。

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        // 创建⼀个哈希表
        unordered_map<int, int> hash; // {arr[i], dp[i]}
        hash[arr[0]] = 1;             // 初始化

        int ret = 1;
        for (int i = 1; i < arr.size(); i++) {
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }
        return ret;
    }
};

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

 注意：严格递增：是只能符合arr[i]<arr[i+1]的！！

1.状态表示

对于线性动态规划问题，我们通常根据“经验+题目要求”来定义状态表示。

• 以某个位置为结尾，巴拉巴拉；
• 以某个位置为起点，巴拉巴拉。

在这里，我们选择以某个位置为结尾来定义状态

• dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦序列」中，最⻓的斐波那契⼦数列的⻓度。

但是这⾥有⼀个⾮常致命的问题，那就是我们⽆法确定i结尾的斐波那契序列的样⼦。这样就会导 致我们⽆法推导状态转移⽅程，因此我们定义的状态表⽰需要能够确定⼀个斐波那契序列。

斐波那契数列的特性是，仅需知道序列里面的最后两个元素，就可以确定这个序列。于是，我们修改状态表示为：

• dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，最长的斐波那契子序列的长度。规定 i < j。

2.状态转移方程：

我们设 nums[i] = b 和 nums[j] = c，这两个元素分别是我们当前考虑的斐波那契子序列的最后两个元素。接下来，我们需要根据前一个元素 a 的情况来讨论状态转移：

我们仔细看这个图就会发现有3种情况

1. 情况一：也就是a<b时，此时a 存在，且其下标为 k，满足 a = c - b。

   • 在这种情况下，我们需要检查 a 是否小于 b（即 a < b），因为斐波那契数列是严格递增的（除了最开始可能存在的 0, 1 这种情况，但在这里我们所有元素都是正数，因此不考虑 0）。
   • 如果 a < b 成立，那么说明我们可以将 a, b, c 这三个元素构成一个斐波那契子序列。此时，我们需要找到以 a 和 b 结尾的最长斐波那契子序列的长度，然后在这个长度的基础上加上 c 这个元素，即 dp[i][j] = dp[k][i] + 1。

2. 情况二：也就是 b < a < c时。

   • 在这种情况下，虽然 a、b 和 c 三个元素都在数组中，但它们不能构成一个斐波那契子序列（因为斐波那契数列是严格递增的，且每个数是前两个数的和，所以不可能出现 b < a < c 的情况，除非 a 不是 b 和某个前面元素的和）。因此，此时 b 和 c 只能自己组成一个长度为 2 的“子序列”（虽然不满足斐波那契数列的定义，但在这里我们暂时将其视为一个可能的子序列片段）。所以，dp[i][j] = 2。

3. 情况三：a 不存在。

   • 在这种情况下，b 和 c 两个元素在数组中找不到满足 a = c - b 的前一个元素 a。因此，同样地，b 和 c 只能自己组成一个长度为 2 的“子序列”。所以，dp[i][j] = 2。

优化点：

在状态转移方程中，我们需要确定 a 元素的下标。因此，我们可以在动态规划之前，将所有的“元素+下标”绑定在一起，放到哈希表中，以便快速查找。

初始化：

将 dp 表中的值都初始化为 2，因为任意两个元素都可以组成一个长度为 2 的斐波那契子序列（虽然不满足斐波那契数列的严格定义，但在此作为初始状态）。

填表顺序：

1. 先固定最后一个数 c（即 nums[j]）。
2. 然后枚举倒数第二个数 b（即 nums[i]）。

返回值：

因为不知道最终结果以谁为结尾，因此返回 dp 表中的最大值 ret。但是 ret 可能小于 3，小于 3 的话说明不存在满足条件的斐波那契子序列（因为斐波那契子序列至少要有三个元素）。因此，需要判断一下，如果 ret < 3，则返回 0，否则返回 ret。

class Solution 
{
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        int n = arr.size(); // 获取数组的大小

        // 使用哈希表来存储数组元素的值和它们的索引，以便快速查找某个值在数组中的位置
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++) 
            hash[arr[i]] = i;

        int ret = 2; // 初始化最长斐波那契子序列的长度为2（最小的可能长度）
        
        // 使用二维动态规划数组dp，dp[i][j]表示以arr[i]和arr[j]为结尾的最长斐波那契子序列的长度
        vector<vector<int>> dp(n, vector<int>(n, 2));

        // 固定最后一个位置j，从数组的第二个元素开始遍历到倒数第二个元素
        for(int j = 2; j < n; j++) 
        {
            // 固定倒数第二个位置i，从数组的第一个元素开始遍历到j-1
            for(int i = 1; i < j; i++) 
            {
                // 计算可能的斐波那契子序列中的前一个元素a的值
                int a = arr[j] - arr[i];

                // 如果a小于arr[i]（保证斐波那契数列的递增性质），并且a在哈希表中存在（即a是数组中的一个元素）
                if(a < arr[i] && hash.count(a)) 
                {
                    // 更新dp[i][j]为以a, arr[i], arr[j]为结尾的斐波那契子序列的长度（即dp[hash[a]][i] + 1）
                    dp[i][j] = dp[hash[a]][i] + 1;

                    // 更新最长斐波那契子序列的长度
                    ret = max(ret, dp[i][j]);
                }
            }
        }

        // 如果最长斐波那契子序列的长度仍然为2（即没有找到长度大于2的斐波那契子序列），则返回0
        // 否则，返回最长斐波那契子序列的长度
        return ret < 3 ? 0 : ret;
    }
};

题目七——1027. 最长等差数列 - 力扣（LeetCode）

1.状态表示：

对于线性动态规划问题，我们通常会根据“经验+题目要求”来定义状态表示。这里有两种常见的定义方式：

• i. 以某个位置为结尾，描述某种性质或结果；
• ii. 以某个位置为起点，描述某种性质或结果。

在这里，我们选择较为常用的方式，即以某个位置为结尾来定义状态。但直接以某个位置为结尾来描述等差序列的长度会面临一个问题：我们无法准确确定这个以i结尾的等差序列的具体样子。这将导致我们无法推导出状态转移方程。

因此，我们需要一个能够唯一确定等差序列的状态表示。根据等差序列的特性，知道序列中的最后两个元素就足以确定整个序列。所以，我们修改状态表示为：

• dp[i][j] 表示：以i位置和j位置的元素为结尾的所有子序列中，最长的等差序列的长度。这里，i < j，以确保i和j分别代表序列中的两个不同位置。

这样的状态表示能够唯一确定一个等差序列，并允许我们根据已知信息推导出状态转移方程。

2.状态转移方程

 我们设 nums[i] = b 和 nums[j] = c，这两个元素分别是我们当前考虑的斐波那契子序列的最后两个元素。接下来，我们需要根据前一个元素 a 的情况来讨论状态转移：

我们仔细看这个图就会发现有3种情况

a. 此时a<b，那么a 存在，下标为 k，并且 a = 2 * b - c。

• 如果 a < b：此时我们需要以 k 位置以及 i 位置元素为结尾的最长等差序列的长度，然后再加上 j 位置的元素即可。于是 dp[i][j] = dp[k][i] + 1。这里因为会有许多个可能的 k，我们仅需离 i 最近的满足条件的 k 即可。

b. 此时b<a<c，这个是不允许的：

• 此时只能两个元素 b 和 c 自己玩了，因为无法找到一个有效的 a 来形成更长的等差序列。所以 dp[i][j] = 2。

c. a 不存在：

• 此时依旧只能两个元素 b 和 c 自己玩了，因为没有前一个元素 a 可以形成等差序列。所以 dp[i][j] = 2。

优化点：

我们发现，在状态转移⽅程中，我们需要确定 a 元素的下标。因此我们可以将所有的元素+ 下标绑定在⼀起，放到哈希表中，这⾥有两种策略：

• a. 在 dp 之前，放⼊哈希表中。这是可以的，但是需要将下标形成⼀个数组放进哈希表中。这样 时间复杂度较⾼，我帮⼤家试过了，超时。
• b. ⼀边 dp ，⼀边保存。这种⽅式，我们仅需保存最近的元素的下标，不⽤保存下标数组。但是 ⽤这种⽅法的话，我们在遍历顺序那⾥，先固定倒数第⼆个数，再遍历倒数第⼀个数。这样就 可以在 i 使⽤完时候，将 nums[i] 扔到哈希表中。

3. 初始化：

根据实际情况，可以将所有位置初始化为 2 。

4. 填表顺序：

• a. 先固定倒数第⼆个数；
• b. 然后枚举倒数第⼀个数。

使用上面这种方案，存粹是为了配合我们的那个优化方案

5. 返回值：

由于不知道最⻓的结尾在哪⾥，因此返回 dp 表中的最⼤值。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // 获取数组的长度
        
        // 使用哈希表存储数组元素及其索引，初始时只将第一个元素的索引存入
        unordered_map<int, int> hash;
        hash[nums[0]] = 0;
 
        // 使用二维动态规划数组dp，dp[i][j]表示以nums[i]和nums[j]为结尾的最长等差子序列的长度
        // 初始化为2，因为任何两个元素都可以构成一个长度为2的等差子序列
        vector<vector<int>> dp(n, vector<int>(n, 2));
        
        int ret = 2; // 记录最长等差子序列的长度，初始化为2
 
        // 遍历数组，从第二个元素开始，因为需要找到它之前的元素来构成等差子序列
        for (int i = 1; i < n; i++) {
            // 对于每个nums[i]，再遍历它之后的元素nums[j]
            for (int j = i + 1; j < n; j++) {
                // 根据等差数列的性质，计算中间项a的值
                int a = 2 * nums[i] - nums[j];
                
                // 如果哈希表中存在a，说明可以构成一个等差子序列
                if (hash.count(a)) {
                    // 更新dp[i][j]为以nums[hash[a]]、nums[i]和nums[j]为结尾的等差子序列的长度
                    dp[i][j] = dp[hash[a]][i] + 1;
                    
                    // 更新最长等差子序列的长度
                    ret = max(ret, dp[i][j]);
                }
            }
            
            // 将当前元素nums[i]的索引存入哈希表，以便后续查找
            hash[nums[i]] = i;
        }
 
        // 返回最长等差子序列的长度
        return ret;
    }
};

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

1.状态表示

对于线性dp，我们可以用「经验+题目要求」来定义状态表示：

• 以某个位置为结尾，巴拉巴拉；
• 以某个位置为起点，巴拉巴拉。

这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义一个状态表示：

• dp[i] 表示：以i位置元素为结尾的「所有子序列」中，等差子序列的个数。

但是这里有一个非常致命的问题，那就是我们无法确定i结尾的等差序列的样子。这样就会导致我们无法推导状态转移方程，因此我们定义的状态表示需要能够确定一个等差序列。

根据等差序列的特性，我们仅需知道序列里面的最后两个元素，就可以确定这个序列的样子。因此，我们修改我们的状态表示为：

• dp[i][j] （注意我们规定i < j）表示：以i位置以及j位置的元素为结尾的所有的子序列中，等差子序列的个数。

2.状态转移方程

设 nums[i] = b 和 nums[j] = c，其中 i < j。我们要找的是以 nums[i] 和 nums[j] 结尾的所有等差子序列的个数，记作 dp[i][j]。

根据等差数列的性质，如果 nums[a]、nums[i] 和 nums[j] 形成一个等差数列，那么有 2 * nums[i] - nums[j] = nums[a]。这里的 a 是我们想要找到的前一个等差数列的结尾元素的索引。

按道理来说a会有下面三种情况

但是我们是以i,j为结尾的，所以直接排除后面两种情况

现在，我们分两种情况讨论：

a. 存在 a：

• 假设 a 存在，并且 a < i（因为 a 需要在 i 之前），同时 nums[a] = 2 * b - c。
• 此时，我们知道以 nums[a] 和 nums[i] 结尾的等差子序列的个数是 dp[a][i]。
• 如果我们在这些子序列的末尾加上 nums[j]，它们仍然构成等差数列。因此，对于每一个以 nums[a] 和 nums[i] 结尾的等差子序列，我们都可以得到一个以 nums[i] 和 nums[j] 结尾的新等差子序列。
• 除此之外，nums[a]、nums[i] 和 nums[j] 本身也构成一个新的等差子序列。
• 因此，我们需要将 dp[a][i] 的值累加到 dp[i][j] 上，并额外加1来表示这个新的等差子序列。
• 此外，这个可能有很多个a都符合条件，那我们需要将其累加起来。
• 状态转移方程为：dp[i][j] += dp[a][i] + 1（注意，这里实际上是在遍历所有可能的 a 值，并将它们对应的 dp[a][i] 值累加到 dp[i][j] 上）。

b. 不存在或未遍历到 a：

• 如果 a 不存在（即 nums[a] = 2 * b - c 在数组中找不到对应的 a），或者在当前遍历过程中还未遍历到 a，则 dp[i][j] 的值暂时不会由 dp[a][i] 贡献。
• 但是，随着遍历的进行，当遍历到 a 时，上面的状态转移方程会确保 dp[i][j] 被正确地更新。

需要注意的是，由于我们是从前向后遍历数组来构建 dp 数组的，因此当计算 dp[i][j] 时，所有可能的 dp[a][i]（其中 a < i < j）都已经被计算过了。这保证了状态转移方程的正确性。

优化

另外，我们知道会有多个a都符合情况，那我们是不是可以通过一点优化来简化我们的搜索操作呢？

我们通常使用一个哈希表（或称为字典、映射）来存储数组中每个元素的值和对应的索引。

但是由于要处理多个a符合的情况，我们使用unordered_map<long long,vector<int>>来存储，键就存储元素的值，而值就存对应的数组元素的下标。

这样子如果我们找到了符合条件的值tmp，我们就遍历hash[tmp]，然后一一判断是不是小于i即可。

3. 初始化：

刚开始是没有等差数列的，因此初始化 dp 表为 0 。

4. 填表顺序：

• a. 先固定倒数第⼀个数；
• b. 然后枚举倒数第⼆个数。

5.返回值：

我们要统计所有的等差⼦序列，因此返回 dp 表中所有元素的和。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        // 获取数组的大小
        int n = nums.size();
        
        // 使用哈希表来存储每个元素值及其对应的所有索引
        // 这样我们可以快速找到满足等差数列条件的前一个元素的位置
        unordered_map<long long, vector<int>> hash;
        for (int i = 0; i < n; i++) {
            hash[nums[i]].push_back(i);
        }
        
        // 创建一个二维动态规划数组，dp[i][j] 表示以 nums[i] 和 nums[j] 结尾的等差子序列的个数
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 初始化等差子序列的总数为0
        int sum = 0;
        
        // 从长度为3的子序列开始遍历（因为等差数列至少需要3个元素）
        for (int j = 2; j < n; j++) {
            for (int i = 1; i < j; i++) {
                // 计算等差数列中前一个元素的值
                long long tmp = (long long)2 * nums[i] - nums[j];
                
                // 检查哈希表中是否存在这个值
                if (hash.count(tmp)) {
                    // 遍历所有满足条件的索引 k
                    for (auto k : hash[tmp]) {
                        // 如果 k 在 i 之前，说明 nums[k]、nums[i]、nums[j] 可以构成一个等差数列
                        if (k < i) {
                            // 根据状态转移方程更新 dp[i][j]
                            dp[i][j] += dp[k][i] + 1;
                        } else {
                            // 如果 k 不在 i 之前，就无需继续检查了，因为哈希表中的索引是按顺序存储的
                            break;
                        }
                    }
                }
                // 将当前计算出的等差子序列个数加到总数中
                sum += dp[i][j];
            }
        }
        
        // 返回等差子序列的总数
        return sum;
    }
};