【动态规划】子序列问题二（数组中不连续的一段）

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.最长定差子序列

题目链接： 1218. 最长定差子序列

题目分析：

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

算法原理：

1.状态表示

经验 + 题目要求

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

2.状态转移方程

设 i 位置里面元素为a，如果以 i 位置元素为结尾研究最长等差子序列的长度，其实 i 位置前面那个元素已经确定了，这道题和最长递增子序列是有区别的，那道题 i 位置前面的元素是要从前往后遍历一遍的来找倒数第二个元素在哪里。这道题已经告诉我们相邻两个元素的差是diff，我只要知道最后一个元素就能推出倒数第二个元素。设倒数第二个元素为b。 a - b = diff —> b = diff - a。

根据 b 存不存在可以分两个情况：

b不存在，a本身就是

b存在，因为是乱序的，前面可能有很多元素等于b，其实我们只需要考虑最后一个b元素的位置就可以了。因为我们想要的是以b元素为结尾的最长等差子序列的长度，最后一个b元素所在位置dp[j1]里面的值至少大于等于前面以b元素为结尾最长等差子序列的长度。然后加上 i 位置的元素。

这里有个优化：

虽然我们是可以从后往前遍历找到最后一个b元素所在的位置的，但是我们可以这也做，可以之间把 b 元素 和它对应的 dp[i] 放在hash表。就不用去遍历了，可以O(1)的时间复杂度就找到。

1. 将 元素 + dp[j] 的值，绑定放进哈希表中

甚至我们还可以将 a 元素 + dp[i] 绑定放进哈希表。这样的话就不用要哈希表了。

2. 直接在哈希表中，做动态规划

3.初始化

我们只需要将以第0个位置元素为结尾子序列，最长的等差子序列的长度初始化一下就行了，反正没得选，就是自己本身。

dp[arr[0]] = 1

4.填表顺序

从左往右

5.返回值

我们要返回的是最长的等差子序列长度，但是这个长度可能在dp表里任意一个位置，因此返回 dp 表里面的最大值

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

        // 创建 dp 表
        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]]保证b是最新的值
            //hash[arr[i] - difference]保证如果不存在value是0
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret,hash[arr[i]]);
        }
        return ret;

    }
};

2.最长的斐波那契子序列的长度

题目链接： 873. 最长的斐波那契子序列的长度

题目分析：

满足斐波那契数列条件，元素长度大于等于3，还有从第三个元素开始，每个元素都等于前两个元素的和，如果序列满足这两个条件我们就称之为斐波那契数列。

注意这道题给的是严格递增，不仅是递增的而且元素还是不重复的。填表的时候有优化的作用。

算法原理：

1.状态表示

经验 + 题目要求

dp[i] 表示：以 i 位置元素为结尾所有子序列中，最长斐波那契数列子序列的长度

我们尝试用这个状态表示来看看能不能推导出来状态转移方程。

我们是 i 位置来划分问题的，在 0 ~ i -1 任选一个位置 j ，通过 j 位置的 dp[j] ，来更新出 i 位置的dp[i]，这是之前做子序列的方法。但是这道题就不行了。我们的状态表示只是表示出来最长斐波那契数列子序列的长度，但是并不知道具体的斐波那契序列。其实如果我们知道最后两个位置的值nums[j]，nums[i]，我们是能推导出来在前面一个位置的。但是dp[j]根本不知道这个斐波那契数列是什么样。所有我们不能直接用dp[j]的值去更新dp[i]的值。所以上面的状态表示不对！

通过刚才的分析我们发现，如果在一个斐波那契数列知道最后两个元素，其实是可以把前面所有的元素都推出来的。 … a-(b-a)，b-a，b，a。既然单独一个位置为结尾推不出来斐波那契子序列长什么样子，但是如果能用两个元素为结尾就能推出斐波那契子序列长什么样子。一维解决不了问题，在扩一维。

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

2.状态转移方程

如果我们以最后两个位置为结尾，其实我们是可以直接知道倒数第三个数，设倒数第三个数为 a， a = c - b，设 a 的下标为 k

根据a可以分下面三种情况：

1. a不存在
2. a存在且b<a<c
3. a存在且a<b

a不存在，根本构不成斐波那契子序列，dp[i][j]本应该是0的，但是dp[i][j] 表示以 i，j位置为结尾，至少有两个元素。所以给2。如果dp里面都是2说明，没有都没有构成斐波那契子序列，最后直接返回0就可以了。

a存在且b<a<c，a虽然存在，但是在bc中间，不符合斐波那契数列，所以也是给2。

a存在且a<b，我们要的是最长斐波那契子序列长度，先把 k 位置元素拿出来，，在把 i 位置元素拿出来，先找到以着两个位置元素为结尾的最长斐波那契子序列，后面在加上一个j位置元素就可以了。 而以ki位置元素为结尾最长斐波那契子序列正好在dp[k][j]中，然后再加上1

优化：找a元素所在位置比较花时间，因此我们将数组中所有元素与它们的下标绑定，存在哈希表中。（数组里面的元素是严格递增，不会存在重复元素）

3.初始化

表里面所有的值都初始化为2，就不用考虑前面两种情况了。
但是细心的会发现不能把表里面的值都初始化为2，dp[0][0] 相当于里面就一个元素，里面的值就是1。其实我们在状态表示就已经规定好了 i < j。对于这个二维dp表，我们只会用到上半部分，

4.填表顺序

从上到下，从左到右

5.返回值

dp表里面的最大值 ret , 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;
        vector<vector<int>> dp(n,vector<int>(n,2));
        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;
                ret = max(ret,dp[i][j]);// 统计表中的最⼤值
            }
        }

        return ret < 3 ? 0 : ret;
    }
};

3.最长等差数列

题目链接： 1027. 最长等差数列

题目分析：

在数组中找一个子序列，这个子序列要是最长的等差子序列，返回长度。

算法原理：

1.状态表示

经验 + 题目要求

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

接下来以这个状态表示分析一下：能推导出来状态转移方程说明这个状态表示是对的，推导不出来说明这个状态表示是错的。

我想求 以 i 位置元素为结尾的 dp[i] 的值，根据以往的经验 要去 0 ~ i - 1 位置找dp[j]去更新dp[i]，但是这道题不行，这道题要找的是 最长的等差序列的长度。而dp[i-1]表示以 i -1 位置元素为结尾的所有子序列中，最长的等差序列的长度。我只知道长度，并不知道等差子序列是什么，这个 i 到底能不能跟在 j 后面是不知道的！因此上面状态表示不对。

如果我们知道等差序列最后两个元素，我们就知道把这个等差序列前面所有元素都推出来，设倒数第一个位置是 a ，倒数第二个位置是 b， 倒数第三个位置为 x，x = 2*a-b。

因此我们的状态表示：

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

2.状态转移方程

设倒数第二个位置 i 位置元素为 b，倒数第一个位置 j 位置元素为 a，我们可以推出来倒数第三个位置 k 位置元素为 a = 2b -c

根据倒数第三个 k 位置可以分为三种情况：

1. a不存在
2. a存在，i < k < j
3. a存在，k < i

a不存在以及a存在，i < k < j（a在bc中间），单独bc就能构成等差子序列，因此长度为2

a存在，k < i（a < b，在i 位置左边），但是这里又有很多种情况这个a可能有很多个。那这个时候我们需要把所有情况都考虑吗。其实不需要，假设前面最长子序列是以a元素为结尾，那最后一个a所在位置的长度至少大于等于前面的a的长度。所有我们只考虑离 i 位置最近的a就可以了。我们的 k 也表示的是左边离 i 位置最近的那个下标。

dp[i][j] 表示以 ij 为结尾的最长子序列的长度，这个时候如果发现倒数第三个元素存在并且i左边，是不是可以先找到以 ki 为结尾的最长的长度，然后加一个 j 位置元素就行了，而以 ki 为结尾的最长的长度正好就是 dp[k][i]

还没完，有没有发现我们找下标k并不是O(1)的时间复杂度。本来dp[i][j] 时间复杂度就已经是O(N ^ 2)，又来了一层循环，时间复杂度就变成 O(N ^ 3)。

优化一下：我们要找到的是离 i 位置最近a元素的下标

1. 在 dp 之前将所有元素 + 下标绑定，放在hash表中，<元素，下标数组>(适合数组中无重复元素)。但是如果这个数据非常恶心，它会把下标数组搞得非常大，时间复杂度依旧是O(N ^ 3)。
   2.一边 dp，一边保存离它最近的元素的下标，<元素，下标>(适合数组中有重复元素)。 这样就是O(1)时间复杂度。

选第二种方式写代码有技巧和填表顺序有关，我们先分析下面的。

3.初始化

表里面所有的值都初始化为2，就不用考虑前面两种情况了。
但是细心的会发现不能把表里面的值都初始化为2，dp[0][0] 相当于里面就一个元素，里面的值就是1。其实我们在状态表示就已经规定好了 i < j。对于这个二维dp表，我们只会用到上半部分，

4.填表顺序

我们是以i j 位置为结尾，填表也有两种方法：

第一种：

1. 先固定倒数第一个数
2. 枚举倒数第二个数

先固定最后一个数 j，枚举倒数第二个数也就是说 i 位置是从0 开始到 j - 1 。当 i = 0 算一下 dp[i][j]，当 i = 1 算一下 dp[i][j] 。。。

第二种：

1. 先固定倒数第二个数
2. 枚举倒数第一个数

先固定 i，让 j 从 i + 1 位置开始往后枚举。

那我们选哪种策略呢？回到优化，一边 dp，一边保存离它最近的元素的下标，<元素，下标>(适合数组中有重复元素)。 如果选择第一种策略会有一种问题，i 位置是一直移动的，那最近的元素也是在一直改变。很难保证是最近的。 所以我们选择第二种初始化方式。当我们固定 i 位置之后，j是往后移动的。当把 i 位置填完之后，ij都会往后移动，我们就可以把i位置的元素存到hash表里。

所以我们选择第二种填表顺序，当 i 位置填完之后，将 i 位置的值放入到hash表中即可。

5.返回值

dp[i][j] 表示以 ij 为结尾的最长子序列的长度，题目要求的是整个子序列中最长的那个。所以返回 dp 表中的最大值。

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        
        //优化
        unordered_map<int,int> hash;
        hash[nums[0]] = 0;

        int n = nums.size();
        vector<vector<int>> dp(n,vector<int>(n,2));//创建 dp 表 + 初始化
        int ret = 2;
        for(int i = 1; i < n - 1; ++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;

    }
};

4.等差数列划分 II - 子序列

题目链接： 446. 等差数列划分 II - 子序列

题目分析：

给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。

如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。

算法原理：

1.状态表示

经验 + 题目要求

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

接下来就以这个状态表示看看能不能分析出状态转移方程

以 i 位置元素为结尾的子序列，根据前面的经验 ，有可能是自己本身，有可能是前面 0 ~ i - 1 区间 dp[i - 1]，dp[i - 2] … dp[0] 去更新dp[i]进而得到状态转移方程。dp[i - 1] 对应 i - 1 位置元素，dp[i - 2] 对应 i - 2 位置元素… 。，这道题我们要的是等差子序列，要的是 i 位置跟在这些元素的后面，我们的状态表示只是等差子序列的个数，i 位置跟在前面元素后面形成等差子序列，必须要是能跟才行。这个状态表示，我们只知道子序列的个数，但是不能确定一个具体的子序列。 因此这个状态表示不对。重新定义一个状态表示。我们如果等差子序列最后两个位置元素就可以把整个等差子序列推出来了。因此状态表示可以这样定义

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

2.状态转移方程

设倒数第二个位置 i 位置元素为b，倒数第一个位置 j 位置元素为 c，倒数第三个位置 k位置 元素为a ， a = 2b - c

根据 a 可以分三种情况：

1. a不存在
2. a存在，i < k < j
3. a存在，k < i

a不存在，a存在，i < k < j 构不成等差子序列，给0就行了

a存在，k < i，但是这里又有很多种情况这个a可能有很多个。是全都都考虑还是只考虑最后一个位置的a呢？注意我们这里要的是等差子序列的个数，并不是最长等差子序列长度等等。bc可以和前面任意一个a构成等差子序列，因此我们都要考虑。

dp[i][j] 表示以 ij 为结尾的等差子序列的个数，这个时候如果发现倒数第三个元素存在并且i左边，是不是可以先找到以 ki 为结尾的等差子序列个数，然后加一个 j 位置元素就行了，而以 kx i 为结尾的等差子序列个数正好就是 dp[kx][i]然后在加上 j 位置，注意这里求的是个数，因此 dp[i][j] += dp[ki][i] + 1

这里有个优化：a可能是由重复的，dp[i][j]时间复杂度是O(N ^ 2)，如果在遍历去找a时间复杂度就是O(N ^ 3)了，因此

在dp之前，将<元素，下标数组>绑定在一起，放在哈希表中。

3.初始化

最差情况下就是 i j 位置元素为结尾不构成等差子序列，所以可以把dp表里面所有的值都初始化为0

4.填表顺序

1. 固定倒数第一个数
2. 枚举倒数第二个数

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);

        vector<vector<int>> dp(n,vector<int>(n));//创建 dp 表 + 初始化
        int ret = 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];//处理数据溢出
                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;
        

    }
};