【ONE·基础算法 || 动态规划（二）】

总言

  主要内容：编程题举例，熟悉理解动态规划类题型（子数组、子序列问题）。
  
  
  
  
  

5、子数组问题（数组中连续的一段）

5.1、最大子数组和（medium）

  题源：链接。

5.1.1、暴力

  两层for循环，统计每次求出的最大值。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int ret = -0x3f3f3f;// 用于获取所有层子数组和
        for(int i = 0; i < n; ++i)
        {
            int sum = 0;
            int curmax = -0x3f3f3f; // 用于统计当前层的最大子数组和
            for(int j = i; j < n; ++j)
            {
                sum += nums[j];
                curmax = max(sum,curmax);
            }
            ret = max(curmax,ret);
        }
        return ret;
    }
};

5.1.2、前缀和

  用一个变量记录历史的最小前缀和，在求第j个位置的前缀和时，与历史前缀和做差。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int min_sum = 0;//维护一个最小前缀和
        int sum = 0;//用于统计当前前缀和
        int ret = -0x3f3f3f;// 返回
        for(auto n: nums)
        {
            sum += n;//获取当前前缀和
            ret = max(ret,sum - min_sum);//和历史前缀和比较
            min_sum = min(min_sum,sum);//更新历史最小前缀和
        }
        return ret;
    }
};

5.1.3、动态规划

  这里主要分析动态规划解题。

  1）、思路分析
  1、确定状态表示： 根据经验+题目要求，这里我们选择以 i 为结尾，则dp[i]表示，以 i 位置处的元素为结尾的所有连续子数组中，元素和的最大值。如下图所示，以 nums[i] 结尾的子数组可以有多个，而 dp[i] 存储的就是这些子数组中的最大和。

  2、确定状态转移方程： 我们可以将dp[i]的分为以下两种情况：

1、⼦数组的⻓度为1：此时dp[i] = nums[i] ；
2、子数组的长度大于1：此时dp[i]应该等于以i-1做结尾的所有子数组中和的最大值，再加上nums[i], 也就是dp[i-1] +nums[i]

  上述两种情况中，我们需要的是最大值，因此dp[i] = max(nums[i],dp[i-1] +nums[i])
  

  3、初始化： 根据状态转移方程，为了防止填表越界，需要对 i=0 处位置进行初始化。这里，我们可以选择直接初始化，也可以引入虚拟节点。
  此处选择后者，那么需要注意两个事项：
  ①引入虚拟节点后，dp表和原先nums表中的映射关系。写状态转移方程时需要注意。
  ②虚拟节点处填写的值，需要保证后续填表时正确。

  4、填表顺序： 根据状态转移方程，这里填表顺序从左到右。
  

  5、返回值： 由于最大子数组和的结尾我们是不确定的，因此，这里需要返回整个dp表中的最大值。（可以在完成填表后遍历一遍dp表找最大值，也可以边填表边确定dp表中最大值。）
  
  

  2）、题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表：dp[i]表示，以i位置元素为结尾的所有子数组的最大和
        vector<int> dp(n + 1); // 2、初始化：引入虚拟节点，初始化即dp[0] = 0
        int ret = -0x3f3f3f; // 用于返回
        // 3、填表：从左向右填
        for (int i = 1; i < n + 1; ++i) {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = max(dp[i], ret); // 这里，在遍历的同时一并更新dp表中的最大和
        }
        // 4、返回
        return ret;
    }
};

5.2、环形子数组的最大和（medium）

  题源：链接。

5.2.1、题解

  1）、思路分析
  分析题目，可以发现此题和5.1很像，区别在于本题中数组成环，那么，和最大的子区间有以下两种存在形式：

1、和最大的子区间，就在原数组内连续的一段区域上（包括整个数组）;
2、和最大的子区间，出现在原数组内首尾相连的两段上。

  如果是情况一，其思路就和5.1一致了。如果是情况二，其实我们可以稍微逆向思考一下。

  如上图分析，那么实际上我们只需要按照5.1中的思路，分别定义两个dp表，一个求最大元素和，一个求最小元素和即可（对于后者，用总的元素和减去当前求得的最小元素和，即可得到区域在首位两端的子区间的最大元素和）。
  
  

  1、确定状态表示： 根据经验+题目要求，这里以 i 为结尾。则有：

f[i]:以 i 为结尾的所有连续子数组中，元素和的最大值。
g[i]:以 i 为结尾的所有连续子数组中，元素和的最小值。

  2、确定状态转移方程： 5.1中分析过，此处不再重复。

f[i] = max(f[i-1] + nums[i], nums[i]);
g[i] = min(g[i-1] + nums[i], nums[i]);//注意这里求的是最小元素和
// PS：若填表时引入虚拟节点，则此处注意下标映射关系

  
  3、初始化： 这里我们选择引入虚拟节点进行初始化，为了避免下标越界，需要将 i=0 处的位置进行初始化。有 f[0] = 0，g[0] = 0。

  4、填表顺序： 从左往右。

  5、返回值： 注意特殊情况。

  
  
  2）、题解
  时间复杂度：$O(n)$，空间复杂度：$O(n)$。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表，确定状态表示
        vector<int> f(n + 1); // f[i]:以i为结尾的所有连续子数组中的最大和。
        vector<int> g(n + 1); // g[i]:以i为结尾的所有连续子数组中的最小和。那么最大值即sum - g[i]
        // 2、初始化：其实也就是f[0] = g[0] = 0，不写默认就是0

        // 3、填表：从左向右
        int sum = 0;          // 记录nums数值元素总和
        int fmax = -0x3f3f3f; // 记录f表中的最大子数组和
        int gmin = 0x3f3f3f;  // 记录g表中的最小子数组和
        for (int i = 1; i < n + 1; ++i) // 一次更新所有：注意下标映射关系
        {
            sum += nums[i - 1];
            f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
            fmax = max(fmax, f[i]);
            g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
            gmin = min(gmin, g[i]);
        }

        // 4、返回
        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

5.3、乘积最大子数组（medium）

  题源：链接。

5.3.1、题解

  1）、思路分析

  1、确定状态表示： 根据经验+题目要求，这里以 i 为结尾分析。效仿之前 “5.1、最大子数组和” 的思路，我们很自然地想到：

dp[i]: 表示以 i 为结尾的所有连续子数组中，元素乘积的最大值。

初步看来，我们可能会写出如下递推公式：
dp[i] = max(nums[i], dp[i-1]*nums[i])

  但这里需要仔细分析斟酌，这个递归公式在本题真的的适用吗？

  在求解最大子数组和时，dp[i-1] + nums[i] ，加减运算保持了子数组的最大和性质，因为对 i-1 每个的子数组加上 nums[i]，其和的变化是单调的，不会改变原先最大和子数组的位置。

  但在处理乘除运算时，情况就复杂多了。乘法运算具有不同于加法的性质：正负数相乘可能产生负数，负数相乘则可能变成正数。这意味着，当 nums[i] 为负数时，dp[i-1] * nums[i] 的结果可能不仅不是 dp[i] 的最大值，反而可能是最小值（如果 dp[i-1] 是正数）。同理，如果 dp[i-1] 是当前区间内的最小乘积（且为负数），而 nums[i] 也是负数，那么 dp[i-1] * nums[i] 可能会是一个很大的正数，从而成为 dp[i] 的最大值。

  因此，我们不能仅凭 dp[i-1] * nums[i] 来确定 dp[i] 的最大值，还需要考虑 nums[i] 与之前子数组乘积的最小值之间的关系。所以，正确的状态转移需要同时记录到当前位置为止的最大乘积和最小乘积（因为最小乘积乘以负数可能成为最大乘积），从而更全面地处理所有可能的乘积情况。
  

f[i]: 表示以 i 为结尾的所有子区间中的最大乘积。
g[i]: 表示以 i 为结尾的所有子区间中的最小乘积。

  2、确定状态转移方程： 根据上述情况，对于f[i]，也就是以 i 为结尾的所有子数组的最大乘积，可以分为三种形式：

1、nums[i]
2、f[i-1]*nums[i]
3、g[i-1]*nums[i]

  对于后两者最大、最小乘积可能发生转变，但不管如何变化。实则对于f[i]，只需要求三者最大即可。对g[i]，求三者最小。

f[i] = max( max(f[i-1]*nums[i], g[i-1]*nums[i]), nums[i]))
g[i] = min( min(f[i-1]*nums[i], g[i-1]*nums[i]), nums[i]))

  这里，我们展开细节来分析一下（虽然没必要，无非把各种情况组合一下）

最大 × 正数 = 仍旧等于最大
最大 × 负数 = 最小；

最小 × 正数 = 仍旧等于最小
最小 × 负数 = 最大。

  1、对f[i]，以i为结尾的所有子数组的最大乘积：

1、子数组的长度为1，也就是nums[i] ;
2、子数组的长度大于1，nums[i] > 0，此时i位置处的最大值为 nums[i] * f[i-1];
3、子数组的长度大于1，nums[i] < 0，此时i位置处的最大值为 nums[i] * g[i-1];


综上所述，f[i] = max( max(f[i-1]*nums[i], g[i-1]*nums[i]), nums[i]))
(如果nums[i] = 0，所有子数组的乘积均为0，三种情况其实都包含了)

  2、对g[i]，以i为结尾的所有子数组的最小乘积：

1、子数组的长度为1，也就是nums[i] ;
2、子数组的长度大于1，nums[i] > 0，此时i位置处的最小值为 nums[i] * g[i-1];
3、子数组的长度大于1，nums[i] < 0，此时i位置处的最小值为 nums[i] * f[i-1];

(如果nums[i] = 0，所有子数组的乘积均为0，三种情况其实都包含了)
综上所述，g[i] = min( min(f[i-1]*nums[i], g[i-1]*nums[i]), nums[i]))

  
  
  
  3、初始化： 这里，采用引入虚拟节点的方式初始化。此时需要注意两点：
  ①下标的映射关系

// 引入虚拟节点后的状态转移方程：
f[i] = max( max(f[i-1]*nums[i-1], g[i-1]*nums[i-1]), nums[i-1]))
g[i] = min( min(f[i-1]*nums[i-1], g[i-1]*nums[i-1]), nums[i-1]))

  ②虚拟节点的初始值要保证后续填表时的结果正确。根据上述状态转移方程，为了填表时不发生越界，需要将 i = 0 处的位置进行初始化。由于这里是乘法，为了让max、min判断时只选到nums[i-1]， f[0] = g[0] = 1即可。

  
  
  4、填表顺序： 从左往右，两个表⼀起填。

  5、返回值： 返回 f 表中的最⼤值。
  
  
  2）、题解

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表
        vector<int> f(n + 1), g(n + 1);
        // 2、初始化
        f[0] = g[0] = 1;
        // 3、填表
        int ret = INT_MIN;
        for (int i = 1; i < n + 1; ++i) {
            // 后续多个位置要用到相同数值
            int x = nums[i - 1];
            int y = f[i - 1] * x;
            int z = g[i - 1] * x;
            
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
            ret = max(ret, f[i]);
        }
        // 4、返回
        return ret;
    }
};

5.4、乘积为正数的最长子数组长度（medium）

  题源：链接。

5.4.1、题解

  1）、思路分析
  分析题目，我们可以提炼出以下关键信息：需要找到乘积为正数的最长子数组，且这个子数组的长度要尽可能长（注意，这里的“最长”指的是子数组的长度，而非乘积的数值大小，长度最长不代表乘积最大）。

  
  1、确定状态表示： 根据经验+题目要求，这里以 i 为结尾，在5.3中我们分析过，由于乘法运算的性质，会导致同一个子数组，在后续累乘中，正负发生变化。 因此，我们需要定义两个状态数组。如下：

1、f[i]：表示以 i 为结尾的所有子数组中，乘积为正数的最长子数组的长度。
// 首先要是一个连续的子数组，其次要满足数组乘积为正数，最后，f[i]值记录的是这些子数组的最长长度。

2、g[i]：表示以 i 为结尾的所有子数组中，乘积为负数的最长子数组的长度。

  
  
  2、确定状态转移方程： 来回顾一下乘法的基本性质。

正数 × 正数 = 正数
负数 × 负数 = 正数

正数 × 负数 = 负数
负数 × 正数 = 负数

  
  1、对f[i]，分析如下。

  最后将情况汇总一下：

当nums[i] > 0 时， f[i] = f[i-1] + 1;
当nums[i] < 0 时， f[i] = g[i-1] == 0 ? 0 : g[i-1] +1;

  2、对g[i]，同理进行分析。

  最后将情况汇总一下：

当nums[i] > 0 时， g[i] = g[i-1]  == 0 ? 0 : g[i-1] +1;
当nums[i] < 0 时， g[i] = f[i-1];

  3、初始化： 这里，引入虚拟节点进行初始化。注意两个事项：
  ①下标映射关系。

当nums[i-1] > 0 时，f[i] = f[i-1] + 1;
                   g[i] = g[i-1]  == 0 ? 0 : g[i-1] +1;

当nums[i-1] < 0 时，f[i] = g[i-1] == 0 ? 0 : g[i-1] +1;
                   g[i] = f[i-1];

  ②虚拟节点的初始化值，要保证后续填表正确。f[0] = g[0] = 0

  4、填表顺序： 从左往右，两个表一起填。
  

  5、返回值： 题目要求返回最长子数组长度，则其存储在 f 表中，返回 f 表中的最大值（不一定是最后一个位置的值）
  
  

  2）、题解

class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表并初始化
        vector<int> f(n + 1), g(n + 1);
        // 2、填表
        int ret = 0;
        for (int i = 1; i < n + 1; ++i) {
            if (nums[i - 1] > 0) {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if (nums[i - 1] < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1;
            }
            ret = max(ret, f[i]);
        }
        // 3、返回
        return ret;
    }
};

5.5、等差数列划分（medium）

  题源：链接。

5.5.1、题解

  1）、思路分析

  1、确定状态表示： 根据经验+题目要求，这里我们以 i 为结尾。则 dp[i] 表示 以 i 为结尾的子数组中，构成等差数列的个数。
  
  
  2、确定状态转移方程： 根据等差数列的定义和性质，首先能知道的是，如果length < 3 ，不满足构成等差数列的项数，可以直接排除。当length >=3时，我们只需要比较i、i-1、i-2三项是否满足等差数列即可。

  综上，这里状态转移方程为：

// 此处使用了三目运算符直接判断，当然也可以使用if语句分别讨论。
dp[i] = (nums[i - 2] + nums[i] == 2 * nums[i - 1]) ? dp[i-1] + 1 : 0;

  
  
  3、初始化： 这里，我们可以直接进行初始化。根据状态转移方程，这里需要用到前两个位置的元素，但是前两个位置的元素无法构成等差数列，因此dp[0] = dp[1] = 0 。这样一来，从 i =2 开始就是三项，即可代入方程获取值。

  
  
  4、填表顺序： 从左到右。
  
  
  5、返回值： 注意，题目要求返回所有构成等差数列的子数组的个数。而我们的状态表示中，dp[i] 仅存储 i 位置处构成等差数列的子数组个数，因此，这里需要我们返回的是dp表的和。
  
  

  2）、题解

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if(n <3) return 0;// 不满足构成等差数列的项数，可以直接排除

        // 1、创建dp表并初始化：dp[0] = dp[1] = 0 
        vector<int> dp(n);
        // 2、填表
        int sum = 0;
        for(int i = 2; i < n; ++i)
        {
            dp[i] = nums[i] + nums[i-2] == nums[i-1]*2 ? dp[i-1] + 1 : 0;
            sum += dp[i];
        }
        // 3、返回
        return sum;
    }
};

5.6、最长湍流子数组（medium）

  题源：链接。

5.6.1、题解

  1）、思路分析
  先来分析题目中湍流的含义：

  
  1、确定状态表示： 根据经验+题目要求，以 i 为结尾，则 dp[i] 表示，以 i 为结尾的所有子数组中，构成湍流的最长子数组长度。
  根据上述的分析，以 i 为结尾的湍流，可以是上升趋势，可以是下降趋势。我们并不知道前⼀个最长湍流数组的结尾处是递增的，还是递减的。因此，这里的状态表示需要再细化：

f[i]: 以 i 位置元素为结尾的所有⼦数组中，最后呈现"上升状态"下的最⻓湍流数组的⻓度；
g[i]: 以 i 位置元素为结尾的所有⼦数组中，最后呈现"下降状态"下的最⻓湍流数组的⻓度；

  2、确定状态转移方程：

  
  
  3、初始化： 为了防止越界，需要将 i = 0处的位置初始化。根据题目要求，即使是单个结点自身，也构成湍流。因此可以将表内所有元素初始化为1。 我们填表从 i=1位置开始填。
  
  
  4、填表顺序： 从左往右，两个表⼀起填。
  
  
  5、返回值： 由于不确定最终湍流是上升还是下降趋势，因此，这里应该取两表中的最大长度值。
  
  
  2）、题解

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        // 1、创建dp表并初始化
        vector<int> f(n,1),g(n,1);
        // 2、填表
        int fmax = 1;// 自身一个结点也算做湍流，故不存在为0的情况，最少长度为1
        int gmax = 1;
        for(int i = 1; i < n; ++i)
        {
            if(arr[i-1] > arr[i])// 最后一次呈现下降趋势
                g[i] = f[i-1] + 1;
            else if(arr[i-1] < arr[i])// 最后一次呈现上升趋势
                f[i] = g[i-1] + 1;
            // 其它情况：不满足，每次都以i位置作为新的子数组
            // 更新
            fmax = max(fmax,f[i]);
            gmax = max(gmax,g[i]);
        }
        // 3、返回
        return max(fmax,gmax);
    }
};

5.7、单词拆分（medium）

  题源：链接。

5.7.1、题解

  1）、思路分析
  先来确定题目需求，给定的字符串 s ，能否被多个字典单词拼接而成。这意味着我们需要将字符串拆分为一个一个的单词。

  
  1、确定状态表示： 根据经验+题目要求，这里我们以 i 为结尾，则dp[i]表示，从[0,i]区间内的字符串，能否被字典中的单词拼接而成。即，这是一个bool类型的状态表。

dp[i] = true 时, 表示[0,i]区间段内的字符串，存在至少一种拆分方式，能被字典拼接出。
dp[i] = false 时, 表示[0,i]区间段内的字符串无论如何拆分，都不能被字典拼接出。

  
  
  2、确定状态转移方程： 根据上述的状态表示，[0,i]区间实则可以拆分为两部分。一部分是以 i 结尾的最后一个单词。另一部分是其它单词组合。这里，我们设最后一个单词的首下标在 j 位置（ 0<= j <=i），则[0,i]区间段内分为如下两部分：

  因此，对dp[i]，要确定[0,i]区间内的字符串是否能够被字典单词拼接，只需要确定：

1、[j,i]组成的最后一个单词，是否出现在字典中？
2、[0.j-1]区间段内的字符串是否能被字典单词拼接？

  对情况1，我们需要提取子串。substr(j,i-j+1)，对比字典单词进行判断;
  对情况2，其描述正好是dp[j-1]，直接读取dp表状态即可。

所以，dp[i] = (dp[j-1]==true) &&  (substr(j,i-j+1)是否在字典中)
如果二者均为true，则 dp[i] = true。

  
  
  需要注意，最后一个单词的长度，我们是不确定的，即substr(j,i-j+1) && dp[j-1] 存在多种组合方式，这就需要我们遍历寻找。

  
  3、初始化： 根据上述状态方程，为了防止越界，这里需要对i = 0位置处进行初始化。
  在这种字符串、子串问题中，一般我们选择引入虚拟节点进行初始化。同时，为了方便处理下标映射关系，可以给原字符串虚拟结点对应的位置插入一个占位字符（一般选择空串）。这样一来，下标的映射关系就得到了统一，我们只需要考虑虚拟节点的填值问题。

  
  
  4、填表顺序： 从左到右
  
  
  5、返回值： 返回dp[n-1]处的bool值。
  
  

  2）、题解

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash(wordDict.begin(), wordDict.end()); // 哈希表，方便找字典单词

        s = ' ' + s; // 为了方便dp表中引入虚拟节点初始化，下标映射能对得上
        int n = s.size();

        // 1、创建dp表并初始化
        vector<bool> dp(n,false);
        dp[0] = true;

        // 2、填表：注意起始位置
        for (int i = 1; i < n; ++i) {
            // 不断找最后一个单词，以此将[0,i]区间分为两部分进行判断
            for (int j = i; j >= 1; --j) {
                string endstr = s.substr(j, i - j + 1); // 提取最后一个单词
                if (dp[j - 1] && hash.count(endstr))    // 如果都满足条件
                {
                    dp[i] = true; // 说明存在至少一种分割方式，能被字典拼接
                    break; // 这里我们只用判断是否存在即可，不需要找全所有方式
                }
            }
        }
        // 3、返回
        return dp[n - 1];
    }
};

5.8、环绕字符串中唯一的子字符串（medium）

  题源：链接。

5.8.1、题解

  1）、思路分析
  先来分析题目，题目问的是，找出 s 中有多少 不同非空子串 也在 base 中出现。
  由示例2，s = "cac"可以看出，相同的子串只能被计数一次。
  由示例3，s = "zab"可以看出，由于base是无限环绕的，需要考虑……za……此类跨越首尾的情况。

  
  如何判断 s 中的某个子串，是否会出现在 base 中？
  仔细观察 base 这个连续字符串，我们会发现，它的顺序都是固定的，从a→z无限循环。而我们知道a~z这26个字母，相邻两个字符之间，ASCII码相差为1。这就意味着，base中随机挑选出的子串，也要保持这一连续的顺序性。即：

base[i-1]+1 == base[i]

  那么对于za这种跨越首尾的情况呢？我们可以单独对这个衔接部分做处理。也可以做取模运算让z折回到a处。

base[i-1] == 'z' && base[i] == 'a';
(base[i-1] + 1 - 'a') % 26) == (base[i]- 'a');

  上述是对题目性质的分析，下述是对解题方法的分析。这里我们以动态规划解题。动态规划只是给我们一种解题的方法，而这些方法是需要套用在具体题目中的。

  1、确定状态表示： 根据经验+题目要求，这里，以 i 为结尾。那么dp[i]表示，s中，以 i 位置为结尾的所有子串，出现在 base 中的个数。

  2、确定状态转移方程： 有了上述对题目性质的分析，这里状态转移理解起来会顺畅很多。对dp[i]，要找其中的子串，我们可以根据长度划分为两部分：

1、⼦串的长度为 1 ：单独的s[i]，根据题目，这一个字符一定会出现在base中
2、⼦串的长度 > 1 ：此时，只需要判断s[i-1]和s[i]组合是否出现在base中。

  综上：dp[i] = 1 + dp[i - 1]（后者需要判断）
  
  
  3、初始化： 实际上，因为每个单独的字符都出现在 base 中，我们可以直接将 dp 表初始化为1。那么填表时，只需要判断长度大于1的情况：

if(s[i] - 1 == s[i - 1] || (s[i - 1] == 'z' && s[i] == 'a'))
	dp[i] += dp[i - 1];
	// 填dp[i] = dp[i - 1] + 1 也行，+1是指单独的s[i]本身。

  4、填表顺序： 从左到右。

  5、返回值： 这里就需要仔细琢磨。题目要求返回所有出现在base中的子串，若我们直接遍历dp表进行统计，根据示例2，s = "cac"可知，这会导致重复计数。因此，我们需要进行“去重”。
  这里，去重仍旧接用了base字符串的连续性。对某一字符ch，以它为结尾的子串在base中形成的组合是相对固定的。因此我们只需要找长度最长的一个即可。

  对相同字符结尾的dp值，我们仅需保留最大值。因为其余dp 值对应的子串都可以在最大的里面找到。为了方便记录，可以创建一个大小为26 的 hash 数组，遍历dp表，统计出所有字符结尾的最大dp值。
  最后返回该 hash数组统计出的总和。

  
  
  
  2）、题解
  时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        
        // 1、创建dp表并初始化
        int n = s.size();
        vector<int> dp(n,1);
        // 2、填表
        for(int i = 1; i < n; ++i)
        {
            // 判断自身与之前的字符串组合
            if( ((s[i-1] + 1 - 'a') % 26) == (s[i]- 'a'))//利用子串的连续性
                dp[i] += dp[i-1] ;
        }

        // 3、返回结果
        // 3.1、去重
        int hash[26] = {0};
        for(int i = 0; i < n; ++i)
        {
            hash[s[i] - 'a'] = max(hash[s[i]-'a'], dp[i]);
        }
        // 3.2、统计
        int sum = 0;
        for(auto ch : hash)
            sum+= ch;
        
        return sum;
    }
};

6、子序列问题（数组中不连续的一段）

6.0、概念区别：子序列和子数组

  子序列和子数组是处理序列数据时常见的两个概念。
  
  1）、子数组
  子数组（Subarray）：子数组是指从原数组中连续选取的一部分元素组成的数组。

  特点：
  ①连续性： 子数组中的元素在原数组中必须是连续的。
  ②顺序性： 子数组保持原数组中元素的相对顺序。

  示例： 假设有一个数组 arr = [1, 2, 3, 4, 5]，那么 [1, 2, 3]、[3, 4] 和 [5] 都是它的子数组，而 [1, 3, 4] 不是（因为 1 和 3 之间不连续）。
  

  
  2）、子序列
  子序列（Subsequence）：子序列是指从原数组中选取的一部分元素（可以不连续），并且保持它们在原数组中的相对顺序。

  特点：
  ①非连续性： 子序列中的元素在原数组中不必是连续的。
  ②顺序性： 子序列保持原数组中元素的相对顺序。
  ③空序列： 空序列（不包含任何元素的序列）是任何序列的子序列。（但具体是否包含要看题目要求）

  示例： 假设有一个数组 arr = [1, 2, 3, 4, 5]，那么 [1, 3, 5]、[1, 2, 4]、[2] 和 []（空序列）都是它的子序列，而 [1, 4, 2] 不是（因为 4 和 2 的相对顺序被改变了）。
  
  
  

  3）、加深理解
  实际上，从集合的角度，子序列的范围更大，包含了子数组。

  对于一个包含 $n$ 个元素的集合（或数组）：

  子序列的数量： 对于包含 $n$ 个元素的集合，每个元素都有两种可能的状态：要么在子序列中（用 1 表示），要么不在子序列中（用 0 表示）。因此，对于 $n$ 个元素，总共有 $2^n$ 种不同的组合方式，即 $2^n$ 个不同的子序列。这包括了空序列（所有元素都不在子序列中）和原集合本身（所有元素都在子序列中）作为特殊情况。

  
  子数组的数量： 对于包含 $n$ 个元素的数组，其子数组的数量可以通过考虑所有可能的起始点和结束点来计算。数组中的每个元素都可以作为子数组的起始点，而对于每个起始点，子数组可以一直延伸到数组的末尾。因此，对于第 $i$ 个元素（$i$ 从 $1$ 到 $n$），有 $n-i+1$ 个可能的子数组以该元素为起始点（包括只包含该元素本身的子数组和一直延伸到数组末尾的子数组）。

将这些数量相加，我们得到子数组的总数：$(n-0+1)+(n-1+1)+\cdots +(n-(n-1)+1)=1+2+\cdots +n=\frac{n(n+1)}{2}\approx n^2$
​

  
  对比一下这两个函数：

6.1、最长递增子序列（medium）

  题源：链接。

6.1.1、题解

  关于本题的其它解法，见：记忆搜索化。
  

  1）、思路分析

  1、确定状态表示： 根据经验+题目要求，以 i 为结尾，则dp[i]表示：以 i 位置元素为结尾的所有子序列中，最长递增子序列的长度。

  2、确定状态转移方程： 为了找到以 nums[i] 结尾的最长递增子序列，需要考虑所有可能的子序列，并从中选择最长的那个。根据 6.0 中对子序列的分析，可以分为以下两种构建方式：

1、子序列长度为1：在这种情况下，单独的 nums[i] 自身构成一个子序列。
   因此，dp[i] 至少为1，即 dp[i] = 1。
   
2、子序列长度大于1：
   对于 j 在 [0, i-1] 区间中的每一个位置，如果满足 nums[i] > nums[j]，则 nums[i] 可以跟在 nums[j] 后面形成一个更长的递增子序列。
   此时，dp[i] 可以更新为 dp[j] + 1 （这里的+1是因为长度在原先的基础上，增加了1）。
   但是，我们需要确保选择的是所有可能 j 值中使得 dp[j] + 1 最大的那个，因此需要遍历 [0, i-1] 区间内的所有 dp[j] 值。
   因此，dp[i] = max(dp[i], dp[j]+1),其中，0 <= j <= i - 1 && nums[j]< nums[i]。

  
  
  3、初始化： 由于单独1个元素也可以构造子序列，因此，可以直接将dp表初始化为1.

  4、填表顺序： 根据这里定义的状态方程，从左往右填表。

  5、返回值： dp表记录的是以每一个位置为结尾的最长递增子序列，我们要返回其中的最大值。
  

  2）、题解
  时间按复杂度为$O(n^2)$，空间复杂度为$O(n)$。这种解法不算是最优解（贪心+二分）。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表并初始化
        vector<int> dp(n,1);
        // 2、填表
        int ret = 1;//因为我们从i=1开始填表，i=0处只存在一种子序列，即nums[0]
        for(int i = 1; i < n; ++i)
        {
            //在[0,i-1]区间内找对应下标的最长递增子序列，判断加上nums[i]后，是否仍旧满足题目要求
            for(int j = i-1; j >= 0;--j)
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);//由于建表时直接初始化为1，相当于这里也直接对单独一个元素的子序列做了比较
            }
            ret = max(ret,dp[i]);//填表时顺带求最大值
        }
        // 3、返回
        return ret;
    }
};

6.2、摆动序列（medium）

  题源：链接。

6.2.1、题解

  1）、思路分析
  此题的思想和 5.6中的湍流问题基本一致，只是那里求的是最长子数组，这里求的是最长子序列。
  

  1、确定状态表示： 如上图，要构成摆动序列，则要求两两元素之间“上升”（递增）、“下降”（递减）趋势交替进行。
  以 i 为结尾进行状态分析。由于 i 位置的状态趋势需要依赖 [0,i-1] 区间内任意 j 位置的状态趋势，如果仅用一个状态来表示当前位置的最长摆动序列长度，这样无法区分序列是以递增还是递减结尾。因此，我们需要状态表示能表示多一点的信息：要能让我们知道这个最长摆动序列的结尾是递增的还是递减的。

  因此，对于以 i 位置元素为结尾dp表，我们将其定义为两种状态：

1、f[i]: 以 i 位置元素为结尾的所有⼦序列中，最后呈现"上升趋势"时，此时最⻓摆动序列⻓度；
2、g[i]: 以 i 位置元素为结尾的所有⼦序列中，最后呈现"下降趋势"时，此时最⻓摆动序列⻓度；

  2、确定状态转移方程： 在5.6湍流中，对于长度大于 1 的子数组，因为连续性的需求，i 的前一个位置必须是 i-1，我们只用分析 i 与 i-1所呈现的趋势即可。但子序列的形成条件无需元素连续性，以 i 位置为结尾的子序列，前一个位置可以是[0，i-1] 区间内的任意位置。因此，我们不妨设 [0,i-1]区间内的任意位置为 j 。
  根据子序列的构成方式，可以分类讨论：
  ①长度为1时： 单独的 i 位置可以看作是一个长度为1的摆动子序列（题目给定条件）。
  ②长度大于1时： 我们需要找到 j（0 <= j < i）使得 nums[i] 可以接在以 nums[j] 结尾的摆动子序列后面，形成新的摆动趋势。
  
  对f[i]：

1、长度为1时：f[i] = 1

2、长度大于1时：因为以i结尾要呈现"上升"趋势，则需要 nums[j] < nums[i]。 
   在满足这个条件下，j 结尾需要呈现"下降"趋势。因此，最长的摆动序列就是g[j] + 1。
   由于 0 <= j <= i-1，因此我们要找出所有满足条件下的最大的g[j]+1。综上，f[i] = max(g[j] + 1, f[i])

  
  对g[i]：

1、长度为1时：g[i] = 1

2、长度大于1时：因为以i结尾要呈现"下降"趋势，则需要 nums[j] > nums[i]。 
   在满足这个条件下，j 结尾需要呈现"上升"趋势。因此，最长的摆动序列就是f[j] + 1。
   由于 0 <= j <= i-1，因此我们要找出所有满足条件下的最大的f[j]+1。综上，g[i] = max(f[j] + 1, g[i])

  
  3、初始化： 题目表示所有的元素单独自身也能构成一个摆动序列，因此可以将 dp 表内所有元素初始化为 1 。

  4、填表顺序： 从左往右，两表一起填。

  5、返回值： 由于并不清楚最长摆动序列最后呈上升还是下降趋势，因此这里应该返回两个dp表里面的最大值。

  2）、题解
  时间按复杂度为$O(n^2)$，空间复杂度为$O(n)$。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        //if(n <=2) return n;

        // 1、创建dp表并初始化
        vector<int> f(n,1);
        vector<int> g(n,1);

        // 2、填表
        int maxf = 1;// 从 i=1开始遍历，最初i=0时，一个元素也构成摆动序列
        int maxg = 1;
        for(int i = 1; i < n; ++i)
        {
            //j可以是[0,i-1]中任意一个位置
            for(int j = i-1; j>=0; --j)
            {
                if(nums[j] > nums[i])// 最后一次呈现下降趋势
                    g[i] = max(f[j] + 1,g[i]);
                else if(nums[j] < nums[i])// 最后一次呈现上升趋势
                    f[i] = max(g[j] + 1, f[i]);
            }
            maxf = max(maxf,f[i]);
            maxg = max(maxg,g[i]);
        }

        // 3、返回
        return max(maxf,maxg);
    }
};

  这里，也可以直接用一个变量记录两个表中的最大值：

int ret = 1;
ret = max(ret, max(f[i], g[i]));
return ret;

6.3、最长递增子序列的个数（medium）

  题源：链接。

6.3.1、记忆搜索化

  实则会发现这题和力扣第300题，最长递增子序列（medium）相同，只是区别在于那里返回的是最长递增子序列的长度，此处返回的是最长递增子序列的个数。
  
  对300题我们曾使用过记忆搜索化的解法（指路），仿照该题，这里仍旧可以使用记忆搜索化。图方便的话，直接把备忘录修改为键值对pair，同时记录最大长度和最大长度的个数即可。
  需要注意如何更新数据。
  时间按复杂度为$O(n^2)$，空间复杂度为$O(n)$。

class Solution {
    vector<pair<int,int>> demo;// 备忘录：最大长度，最大长度的个数
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        demo.resize(n,{0,0});//对备忘录初始化

        int maxlen = 0;
        int maxlensize = 0;
        for(int i = 0; i < n; ++i)
        {
            pair<int,int> ret = DFS(nums,i);
            if(ret.first > maxlen)// 如果长度更大
            {
                maxlen = ret.first;// 更新最长长度和对应的数量
                maxlensize = ret.second;
            }
            else if(ret.first == maxlen) 
                maxlensize += ret.second;// 如果长度相同，则累加数量
        }
        return maxlensize;
    }

    pair<int,int> DFS(vector<int>& nums, int pos)
    {
        if(demo[pos].first != 0) 
            return demo[pos];// 如果已经计算过，则直接返回结果

        pair<int,int> maxsize = {1,1};// 初始化为长度为1，数量为1：当前pos自身长度
        for(int i = pos + 1; i <nums.size(); ++i)
        {
            if(nums[i] > nums[pos])
            {
                pair<int,int> ret = DFS(nums,i);// 递归找最大路径
                if(ret.first + 1 > maxsize.first) // 如果长度更大，更新最长长度和对应的数量
                {
                    maxsize.first = ret.first + 1;// 注意需要ret.first + 1，才等于当前pos位置的长度
                    maxsize.second = ret.second;
                }
                else if(ret.first+1 == maxsize.first) 
                    maxsize.second += ret.second; // 如果长度相同，则累加数量（路径长度不变）
            }
        }
        demo[pos] = maxsize;// 将结果存入备忘录
        return demo[pos];
    }
};

6.3.2、动态规划

  1）、扩展：一个简单贪心策略
  这里，我们补充一点小知识。给定一个数组，如何只遍历一遍，获得其中最大值的个数？

  首先，要明确的是，在寻找最大值及其个数的过程中，最大值与其个数之间是一一对应的。我们不能仅记录个数而不记录对应的值，因为不记录值就无法判断后续出现的元素是否是新的最大值。常规思路是：先遍历一遍数组，求出最大值；再遍历一次数组，根据最大值统计其出现的次数。

  但这里要求我们只遍历一次数组。实则这种思想我们在上述记忆搜索化的解法中就运用过，这里只是将其提炼出来。

  为了满足这个要求，我们可以使用两个变量：maxval 和 valcount。

maxval：用于记录遍历过程中遇到的数组的最大值
valcount：用于记录该最大值出现的次数

  在遍历数组时，会遇到以下三种情况：

1、当前值 i < maxval：
   当前位置的值不是当前已知的最大值，不满足要求。忽视，继续遍历下一个元素。

2、当前值 i == maxval：
   如果当前位置的值等于当前已知的最大值，那么说明我们找到了另一个与最大值相等的元素。此时，需要更新 valcount 的值(valcount+1)。

3、当前值 i > maxval：
   这意味着找到了一个新的更大的值。此时，需要将 maxval 更新为当前值 i，并且重置 valcount 为1。
   因为从这一刻起，i 成为了新的最大值，并且，我们需要重新统计这个新最大值出现的次数。

  下述，我们在使用动态规划解题时，也需要用到上面这个思想。
  
  

  2）、思路分析

  1、确定状态表示： 先前已经说明，如果不知道递增子序列的长度，是无法统计出该长度下的递增子序列的个数的。因此，解决这个问题需要两个状态，我们可以使用两个dp表分别表示长度、个数。

len[i] ：以 i 位置元素结尾的子序列中，最长递增子序列的"长度"
count[i]：以 i 位置元素结尾的子序列中，具有最长长度的递增子序列的"个数"

  
  2、确定状态转移方程： 思路与6.1题基本一致。

  要求 i 处的最长递增子序列的长度和个数 ，可将其分为两类情况讨论：
  ①、子序列长度为1 时，即仅包含 nums[i] 自身，此时有 len[i] = count[i] = 1
  ②、子序列长度大于1时，需要在 [0,i-1] 区间内，找任意位置 j 处的最长递增子序列，并判断 nums[i] 加其后是否能仍旧构成递增子序列，即是否满足 nums[j] < nums[i] 。

  若满足上述条件，由于 j 位置可以是 [0, i-1] 中的任意值，且 i 位置记录的是最长长度及其个数，故可能存在多个满足条件的 j 位置。对此，需利用前述策略进行记录：

1、当 len[j]+1 < len[i], 表示 j 处递增子序列加 nums[i] 后形成的长度，非当前已知的最长长度，直接忽视。

2、当 len[j]+1 == len[i], 表示 j 处递增子序列加 nums[i] 后，与当前最长长度相同，此时需累加 count[i]。
   即 count[i] += count[j]。( 注意这里不是count[i]++，因为 j 位置处满足该长度的子序列可能不止一个！)
   
3、当 len[j]+1 > len[i], 表示发现了更长的递增子序列，需要更新len[i]并重新记录count[i]。
   即 len[i] = len[j] + 1 , count[i] = count[j]。

  3、初始化： 自身一个元素的情况，也构成递增子序列，此时的长度、个数为1。因此可将两表直接初始化为1。
  

  4、填表顺序： 从左往右
  

  5、返回值： 这里，由于并不清楚最大长度出现的个数具体在dp表中的哪一个位置。因此我们需要遍历dp表，找最大值的个数。
  听起来是不是很熟悉？就是1）中方法策略的再次使用。我们可以使用此方法，在完成填表后，再遍历一次求最长子序列的个数，也可以在填表时一并完成该操作。

  
  
  3）、题解
  时间按复杂度为$O(n^2)$，空间复杂度为$O(n)$。

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        // 1、创建dp表并初始化
        vector<int> len(n,1);
        vector<int> count(n,1);
        // 2、填表
        int maxlen = 1;// 用于记录最终结果，这里初始化为1是因为遍历填表时从i=1开始。 i = 0时，自身长度、个数为1。
        int maxlensize = 1;
        for(int i = 1; i < n; ++i)
        {
            //在[0,i-1]区间中找前一个递增子序列
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])// 满足严格递增的条件下
                {
                    if(len[i] == len[j]+1) // a、长度相同时
                        count[i] += count[j];// 累加个数
                    else if(len[i] < len[j]+1) // b、长度更长了
                    {
                        len[i] = len[j] + 1;// 更新当前i位置处的最长递增子序列长度
                        count[i] = count[j];// 重新计数
                    }
                }
            }
            // 更新最终值
            if(maxlen == len[i]) maxlensize += count[i];// 累加个数
            else if(len[i] > maxlen) 
            {
                maxlen = len[i];// 更新长度
                maxlensize = count[i];// 重新计数
            }
        }
        // 3、返回值
        return maxlensize;
    }
};

6.4、最长数对链（medium）

  题源：链接。

6.4.1、题解

  1）、思路分析
  先分析题目，对于从数对数组 pairs 中挑选出的数对 p1 = [a, b] 、 p2 = [c, d] ，只有当 b < c 时，才满足构造数对链的要求。
  题目要求我们求最长的数对链，如果把每一个数对看作一个独立的元素，能够发现这题的思想和 6.1中求最长递增子序列 很像。如此一来我们就可以仿照6.1中的思想，使用动态规划解题。

  但由示例2可以发现，题目给定的数组对是乱序的，即挑选数对时没有严格从左往右，或从右往左进行选数。我们可以随机挑选。

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

  这就限制了我们使用动态规划的思想。因为动态规划要求 以 i 为结尾思考时，只能依赖 [0,i-1]之间的数据，以 i 为起始思考时，只能依赖 [i+1,n-1]之间的数据。即，填表顺序具有单向性。

  为了解决这个问题，我们可以先对原数组对进行排序，这样就能使得我们在填表时，选数只会依赖 i 一侧的数据。
  为什么排序就能满足条件？
  假如按照升序排序， 设排序后 i = [a,b]，i+1 = [c,d]，那么 a <=c 一定恒成立。又因为题目说明 airs[i] = [left, right] 中， left < right，则有 c < d恒成立，一定有 a < d。这样就能保证 我们不会挑选 i + 1处的数对，让 i 排在其后。

  
  
  以动态规划解题， 剩余思考方式就和 6.1中一致。

  1、确定状态表示： 这里，我们以 i 为结尾，则dp[i]表示，以 i 位置的元素对为结尾的所有数对链中，最长的数对链长度。

  2、确定状态转移方程： 对于dp[i]，遍历所有[0，i-1]区间内数对（用j表示下标），找出所有满足pairs[j][1] < pairs[i][0]的位置。更新 dp[i] 为 dp[j] + 1（表示将 pairs[i] 添加到以 pairs[j] 结尾的数对链后面，形成一条更长的数对链）。因为满足条件的 j 处数对可能有很多个，因此 dp[i] 应取其中较大者。

  3、初始化： 初始化时，所有 dp[i] 都为 1，因为每个数对本身都可以看作一条长度为 1 的数对链。

  4、填表顺序： 根据状态转移方程，从左往右填表。
  
  5、返回值： 根据状态表示，返回dp表中的最大值。
  

  2）、题解

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        // 0、预处理：先排个序(默认就是升序，这里练习一下lambda表达式的用法)
        sort(pairs.begin(), pairs.end(),
             [](vector<int>& a, vector<int>& b) -> bool 
             {
                 if (a[0] == b[0])
                     return a[1] < b[1];
                 return a[0] < b[0];
             });

        // 1、创建dp表并初始化
        int n = pairs.size();
        vector<int> dp(n, 1);

        // 2、填表
        int ret = 1;
        for (int i = 1; i < n; ++i) 
        {
            for (int j = i - 1; j >= 0; --j) 
            {
                if (pairs[j][1] < pairs[i][0]) // 注意这里比较的方式
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(ret, dp[i]);
        }
        // 3、返回
        return ret;
    }
};

6.5、最长定差子序列（medium）

  题源：链接。

6.5.1、动态规划（不做优化版本）

  分析此题，我们能想到的第一思路就是循规蹈矩根据之前的动态规划思路解题。

dp[i]表示:以 i 位置的元素为结尾所有的子序列中，最长的等差子序列的长度。

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {

        int n = arr.size();
        // 1、建表，初始化
        vector<int> dp(n, 1);
        // 2、填表
        int ret = 1; // 用于返回
        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (arr[j] + difference == arr[i]) // 题目给定的性质条件
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(ret, dp[i]);
        }
        // 3、返回
        return ret;
    }
};

  但如果用这种方法提交后，可以看到超时。因为题目给定 1 <= arr.length <= 10^5。这种版本的动态规划时间复杂度为$O(n^2)$。
  
  
  

6.5.2、动态规划（使用hash优化版本）

  1）、问题说明
  之前解决最长递增子序列（LIS）问题时，我们只知道前后两个元素之间是递增的关系，并不知道前一个元素的具体值应该是多少。
  但在本题中，由于明确给定了等差 difference，我们是可以计算出前一个数准确的数值的。

设 i-1 ≥ j ≥ 0, arr[j] + difference = arr[i]
则有：arr[j] = arr[i] - difference 

  因此我们只需要在 [0,i-1] 区间中找到满足上述关系的下标位置即可。

  继续分析，满足该关系式的 j 的位置可能有很多个，我们需要遍历[0,i-1]把它们全都找出来后，获取长度吗？

  
  经过上述分析，至少，我们能够确定，不需要遍历[0,i-1]所有位置，只需要找到[0,i-1]区间中，离 i 处元素最近的、满足 arr[j] = arr[i] - difference 关系的下标 j 处元素即可。那么，我们可以让 j = i-1，从后往前遍历。
  
  但即使是这样，我们只是在找 j 时，缩短了一定的遍历数量，并没有优化两层遍历本身。时间复杂度仍旧为 $O(n^2)$。
  
  

  2）、使用hash表
  实际上，由于前一个位置arr[j]的数值是确定的，在解决本题时，无需遍历寻找 i 的前一个值，我们可以利用哈希表来动态地存储这些状态信息。

  具体做法是：将「元素值，该元素值对应的最长等差子序列长度」作为一个键值对存入哈希表中。这样，每当我们遍历到一个新的元素 arr[i] 时，我们都可以在哈希表中快速地查找是否存在一个元素 arr[j]（j < i）满足 arr[j] = arr[i] - difference。 这样就省略了内层的循环，使得查询 j 位置的时间复杂度为 O(1)。

  
  状态表示： hash[arr[i],dp[i]]：hash表中，存的是arr[i]具体元素值，以及对应的dp[i]，以 i 位置的元素为结尾所有的子序列中，最长的等差子序列的长度。

  分析状态转移方程： 在哈希表中直接定位寻找arr[j] = arr[i] - difference
  ①、如果找到了这样的 arr[j]，说明我们可以将 arr[j] 所在的最长等差子序列“延长”到 arr[i]，从而形成一个更长的等差子序列。此时，我们更新哈希表中 arr[i] 对应的长度为 哈希表中arr[j]对应的长度 + 1。

  ②、如果哈希表中不存在这样的 arr[j]，说明 arr[i] 本身就是一个新的等差子序列的起点。此时，我们在哈希表中为 arr[i] 创建一个新的键值对，并将其长度初始化为 1。
  
  初始化： hash[arr[0]] = 1，只有一个元素时，该元素的最长序等差列长度为1。
  
  

  3）、题解

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {

        // 1、创建hash表用于进行动态规划。
        unordered_map<int,int> hash;// key：记录arr[i]的值，value：对应dp[i]，即以i结尾的最长定差子序列长度
        // 2、初始化
        hash[arr[0]] = 1;// 刚开始的时候，需要把第一个元素放进哈希表中

        // 3、填表
        int ret = 1;// 记录返回值
        for(int i = 1; i < arr.size(); ++i)
        {
            hash[arr[i]] = hash[arr[i] - difference] + 1;// 注意理解.这里直接把找到j、找不到j两种情况一并处理了
            ret = max(ret, hash[arr[i]]);
        }
        // 4、返回：hash表里的最大值
        return ret;
    }
};

  分析理解这里的hash[arr[i]] = hash[arr[i] - difference] + 1：
  1）、当arr[j]，也就是 arr[i] - difference 不存在时，此时有 hash[arr[i]] = 1。
  2）、当arr[j]存在时，此时有 hash[arr[i]] = hash[arr[i] - difference] + 1 ，即 dp[i] = dp[j] + 1。
  3）、先前我们说过，满足条件的 j 下标位置可能有很多个，我们只取 [0,i-1] 中离 j 最近的一个。那么这一条语句，能保证这一要求吗？回答：能保证。在我们从左到右填表的过程中，会多次遍历到 arr[j]，即多次填表 j，hash表中始终保存的是最新一次的 hash[arr[j]]值，也就是离 i 最近的一次 j 。
  (以下举了一个相对极端的例子进行理解）

6.6、 最长的斐波那契子序列的长度（medium）

  题源：链接。

6.6.1、题解

  1）、思路分析

  1、确定状态表示： 以 i 为结尾，通常，我们容易想到dp[i] 表示以 i 位置元素为结尾的所有子序列中，最长的斐波那契子数列的长度。
  但是这样有一个问题，由于斐波那契数的定义X_i + X_{i+1} = X_{i+2}，如果我们想找到一个斐波那契子序列，就需要能够“追溯”到它的前两个元素。而dp[i] 只能告诉我们以第 i 个元素结尾的最长斐波那契子序列的长度，它无法告诉我们这个子序列的前两个元素是什么。这会导致我们不能很好的推导出状态转移方程，因为以最长长度到达arr[i]位置处的子序列存在多个。

  因此，单独的dp[i]无法满足状态表示。

  分析斐波那契数列的性质，对 a + b = c，实则一个序列中，我们只需要知道序列里的最后两个元素/最前两个元素，就可以确定这个序列的样子。

  因此，我们可以以序列中最后两个元素来确定一个斐波那契数子序列。

dp[i][j]：以 i 和 j 位置为结尾的子序列中，最长斐波那契子序列的长度。这里，规定 i < j。

  
  
  
  2、确定状态转移方程： 对于每个 (i, j) 对，我们可以检查是否存在一个 k（k < i）使得 arr[k] + arr[i] = arr[j]。如果这样的 k 存在，那么我们可以将 dp[i][j] 更新为 dp[k][i] + 1（因为我们可以将 arr[k], arr[i], arr[j] 作为一个新的更长斐波那契子序列的结尾）。

  一个优化： 如上图，在填表 dp[i][j] 时，我们需要频繁确定 arr[k] 在数组中是否存在。如果我们不做处理，在实际填表时，这需要我们遍历 [0,i-1] 区间，找寻 k 下标位置。
  为了省去这一层遍历查询，在最初阶段，我们可以使用一个哈希表，记录对应 arr[k] 的值，以及其下标位置。

unordered_map<int, int> hash;
// key值：arr[j] - arr[i]，也就是arr[k]的值
// value值： arr[k]的下标位置 k
// PS ： 题目明确说明 arr 是严格递增的正整数数组，因此不存在多个 arr[k] 的情况。

  
  
  
  3、初始化： 根据dp状态表示，最次情况下，子序列为 { arr[i]、arr[j] }，也就是长度为2。因此，我们可以将dp表内的值全都初始化为 2 。

  
  
  4、填表顺序： 要知道dp[i][j] 的值，需要先知道dp[k][i]的值，由于 k < i ，因此填表顺序从上往下。（每一行的填表顺序不做要求）
  
  5、返回值： 因为不知道最终结果以谁为结尾，因此返回dp表中的最大值ret。
  
  

  2）、题解
  两层循环，时间复杂度为$O(n^2)$。二维dp表，空间复杂度为$O(n^2)$。

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int,int> hash;// 创建hash表：用于辅助快速定位数组中的元素及其下标位置
        for(int i = 0; i < n; ++i)
            hash[arr[i]] = i;

        // 1、建表并初始化
        vector<vector<int>> dp(n,vector<int>(n,2));
        // 2、填表
        int ret = 0;
        for(int j = 2; j < n; ++j)// 确定序列中倒数第一个元素位置
        {
            for(int i = 1; i < n; ++i)// 确定序列中倒数第二个元素位置
            {
                int a = arr[j] - arr[i];// 我们要找寻的元素arr[k]
                if(hash.count(a) && hash[a] < i)// 该元素存在，且满足 k < i < j。如果想要判断快点，由于题目表示严格递增，不存在重复元素，可改为 a < arr[i] && hash.count(a)
                    dp[i][j] = dp[hash[a]][i]+1;
                ret = max(ret, dp[i][j]);
            }
        }
        // 3、返回
        return ret > 2 ? ret : 0;
    }
};

6.7、 最长等差数列（medium）

  题源：链接。

6.7.1、题解

  1）、思路分析
  1、确定状态表示： 分析此题，根据经验+题目要求，若我们以 i 为结尾， dp[i] 表示以 arr[i] 为结尾的最长等差数列的长度，是否可行？ 显而易见，如果只知道长度，我们无法确定以 i 结尾的等差序列的样子，即无法推导出状态转移方程。

  因此我们定义的状态表示需要能够确定一个等差序列。而根据等差数列的性质，我们仅需知道序列中相邻的两个元素，就可以获取到公差，从而推导出整个等差序列的样子。因此，状态表示为:

dp[i][j]表示：以 i、j 位置处的元素（arr[i]、arr[j]）为结尾的所有子序列中，最长的等差序列的长度。规定 i < j。

  2、确定状态转移方程： 对于每个 (i, j) 对，我们可以检查是否存在一个 k（k < i）使得 arr[i] - arr[k] = arr[j] - arr[i]，转换一下形式，有 arr[k] = 2*arr[i] - arr[j] 。如果这样的 k 存在，那么我们可以将 dp[i][j] 更新为 dp[k][i] + 1（即，在原先{ ……，arr[k], arr[i] } 序列的基础上，新增一个元素 arr[j]， 作为一个新的更长的等差序列的结尾）。

  可以看到此题和6.6中的思路很相似，但与之区别的是，本题并没有特殊说明元素唯一。这意味着在数组中，我们进行运算后得到的arr[k] ，可能会在多个下标位置处。这里，我们只用选择[0,i-1]区间中，离 i 最近的一个即可。

  如果我们不做处理，则需要我们遍历寻找 k 位置下标，而在此前需要先定位 i、j 位置，相当于需要 3 层嵌套循环，时间复杂度会很高。
  因此，对于如何寻找 arr[k] ，需要进行优化处理。 正好，此类题由于固定计算公式中，当我们固定好 i 、j 位置时，arr[k] 的值实则就已经确定好了。因此，我们可以使用哈希表，将 {元素值，下标} 映射存放，这样，当我们用公式计算出 arr[k]时，就能快速得出其对应的 dp[i]。
  
  这里有一个问题，在上述我们提到过，arr[k] 对应的元素下标有多个，由于 i 、j 位置也是通过遍历进行固定的，因二者的变动性，导致合法的 arr[k] 的下标也是变动的。

  
  1）、一种方法是，创建一个 hash{元素值，元素值对应下标集合} ，在填表前之前，将存放相同元素值的下标形成一个数组，放进哈希表中。那么在填表时，我们找到对应的 arr[k]，就找到该元素值所在的下标集合。减轻了一定程度的遍历，但仍旧需要遍历下标集合找到合法下标位置。如果题目给定的某一元素 arr[k] 在 超级多的下标位置处 均存在，这就相当于遍历 n 个位置，时间复杂度没得到改善。

  2）、另一种方法是，一遍填表，一遍进行 hash 存值。这样我们只用创建一个 hash{元素值，最新一次下标位置} ，保存最近的元素下标即可。但这种情况下，需要注意遍历填表时，i , j 位置固定谁而枚举谁。
  
  此处顺带把填表顺序分析清楚：
  方法①：固定等差子序列倒数第一个元素 arr[j]，在 [0,j-1] 中，枚举倒数第二个元素 arr[i]。
  方法②：固定等差子序列倒数第二个元素 arr[i]，在 [i+1,n-1] 中，枚举倒数第一个元素 arr[j]。

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

  4、填表顺序： 固定倒数第二个元素 arr[j] ，枚举倒数第一个元素arr[j]。
  

  5、返回值： 由于不知道最长子序列的结尾元素在哪，因此需要返回dp表中最大值。

  2）、题解
  

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();

        // 1、创建dp表并初始化
        vector<vector<int>> dp(n, vector<int>(n, 2));
        unordered_map<int, int> hash; // 用于辅助查值的哈希表。key：元素, value:元素最新一次下标位置
        hash[nums[0]] = 0;//已知的位置，先存到hash表中。

        // 2、填表：规定dp[i][j]中，i < j
        int ret = 2;// 用于记录返回值：题目保证了最少有2个元素
        for (int i = 1; i < n; ++i) // 固定倒数第二个元素
        {
            for (int j = i + 1; j < n; ++j) // 枚举倒数第一个元素
            {
                int a = 2 * nums[i] - nums[j]; // 我们要找的arr[k]
                if (hash.count(a))             // 这里就不用判断 k < i < j了，因为这种填表顺序保证该条件满足。
                    dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i; // 在hash中存入/更新当前位置的元素及其下标
        }
        // 3、返回
        return ret;
    }
};

6.8、等差数列划分II-子序列（hard）

  题源：链接。

6.8.1、题解

  1）、思路分析
  1、确定状态表示： 根据经验+题目要求，这里以 i 为结尾，则 dp[i] 表示，以 i 位置的元素 arr[i] 为结尾的所有子序列中，等差数列的个数。
  在经过上述几题的经验，能知道的是，如上述这样定义状态表示，由于无法确定 i 位置处所构成的各个等差数列，在只知道个数的情况下，无法推导得出状态转移方程。

  由于等差数列的性质，知道两个相邻元素，就能得出公差，从而推导出整个等差数列集合。因此，这里我们以序列中最后两个元素为结尾，定位状态表示：

dp[i][j]：以 i 和 j 位置的元素为结尾（arr[i]、arr[j]）的所有子序列中，等差数列的个数。这里，规定 i < j。

  
  
  2、确定状态转移方程： 根据等差数列的公式，对于每个 (i, j) 对，检查数组中是否存在一个 k（k < i）使得arr[k] = 2*arr[i] - arr[j] 。

  优化：为了方便我们找寻arr[k]值，可以使用hash表，将{元素值，元素值对应下标集合}存放入hash表中。这里，value值之所以是下标集合/下标数组，我们在上图也分析过，我们要统计个数，那么每个满足条件的arr[k]，都要进行统计。
  
  
  3、初始化： 刚开始是没有等差数列的，因此初始化dp 表为0

  
  4、填表顺序： 可以先固定倒数第一个元素，枚举倒数第二个元素。
  
  5、返回值： 此返回dp表中，所有元素的和。
  

  2）、题解
  虽然嵌套了三层遍历，但for(auto k : hash[a])取下标集合时，相对外层两个循环可忽略不计，因此时间复杂度总体而言为 $O(n^2)$。n×n的dp表，以及hash表，空间复杂度为$O(n^2)$。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return 0;

        // 1、创建dp表并初始化
        vector<vector<int>> dp(n,vector<int>(n,0));
        
        unordered_map<long long ,vector<int>> hash;// 优化：用于辅助快速查找元素的哈希表。key:元素，value：下标集
        for(int i = 0; i < n; ++i)
            hash[nums[i]].push_back(i);

        // 2、填表：
        int sum = 0;//统计返回值
        for(int j = 2; j < n; ++j)// 固定倒数第⼀个数
        {
            for(int i = 1; i < j; ++i)// 枚举倒数第⼆个数
            {
                long long a = (long long )2*nums[i] - nums[j];// 获取nums[k].使用long long是因为题目规定的nums[i]取值，这里做运算时可能溢出
                if(hash.count(a))// 对应的值存在
                {
                    for(auto k : hash[a])// 取下标
                    {
                        if(k < i) // 注意，因为是下标集合，这里需要判断取出的下标 k 是否合法
                            dp[i][j] += dp[k][i] + 1;
                    }
                }
                sum += dp[i][j];
            }
        }
        // 3、返回
        return sum;
    }
};

Fin、共勉。