动态规划：子序列问题（C++）

前言

动态规划往期文章:

1. 动态规划入门斐波那契数列模型以及多状态
2. 动态规划路径和子数组问题

子序列问题

1.最长递增子序列中等

链接最长递增子序列

• 题目描述
  

• 做题步骤

1. 状态表示
   对于线性dp我们通常采用下面两种表示:
   (1)以某个位置为结尾……
   (2)以某个位置为起点……
   这两种方式我们通常采用第一种以某个位置为结尾再结合题目要求我们可以定义状态表示为dp[i]以i位置为结尾的所有子序列中最长递增子序列的长度。

2. 状态转移方程
   对于以i位置为结尾的子序列一共有两种可能
   (1)不接在别人后面就自己一个dp[i] = 1
   (2)接在[012……i - 1]这些位置后面设0 <= j <= i - 1能保持子序列递增nums[j] < nums[i]就可以接在该位置后面。
   从0~i - 1枚举j看接在那个位置后面长度最大
   即dp[i] = max(dp[i], dp[j] + 1)

3. 初始化
   每个位置最小都为1全都初始化为1。

4. 填表顺序
   保证填当前状态时所需状态已经计算过填表顺序为从左往右。

5. 返回值
   没法直接确定最长子序列的结尾位置一边dp一边更新最大值。

• 代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        //dp[i]表示以i位置为结尾的最长递增子序列
        vector<int> dp(n, 1);    
       int ret = 1;
        for(int i = 1; i < n; i++)
        {
            //从[0, i-1]看一圈找接在那个符合条件的位置后面可以让子序列最长
            for(int j = 0; j < i; j++)       
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);                         
            //看看能不能更新最大
            ret = max(ret, dp[i]);
        }
        return ret;
        //时间复杂度O(N ^ 2)
        //空间复杂度O(N)
    }
};

2.摆动序列中等

链接摆动序列

• 题目描述
  

• 做题步骤

1. 状态表示
   依据前面的经验我们依据可以定义状态表示为dp[i]以i位置为结尾的所有摆动序列中的最大长度。

2. 状态转移方程
   对于长度大于1的摆动序列其有两种情况
   (1)处于上升状态比如(1, 7, 4, 9)。
   (2)处于下降状态比如(1, 17, 10)。
   因此我们需要同时记录两种状态其中f[i]表示以i位置为结尾并处于上升状态的最长摆动序列长度g[i]表示处于下降状态。
   
   摆动序列分析完了我们再来分析单个位置一共有两种可能
   (1)不接在别人后面自己玩dp[i] = 1
   (2)接在[012……i - 1]这些位置后面设0 <= j <= i - 1。
   ①如果接在j位置后处于上升状态(nums[i] - nums[j] > 0)需要以j位置为结尾并处于下降状态的状态即f[i] = g[j] + 1。
   ②如果接在j位置后处于下降状态(nums[i] - nums[j] < 0)需要以j位置为结尾并处于上升状态的状态即g[i] = f[j] + 1。

3. 初始化
   序列长度最小为1所有位置全都初始化为1。

4. 填表顺序
   保证填当前状态时所需状态已经计算过填表顺序为从左往右。

5. 返回值
   没法直接确定最长摆动序列的结尾所以一边dp一边更新最大值。

• 代码实现

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        //dp[i]表示以i位置为结尾的最长摆动序列长度
        int n = nums.size();
        vector<int> f(n, 1);//处于上升状态
        vector<int> g(n, 1); //处于下降状态
        int ret = f[0]; //记录最终结果
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                int gap = nums[i] - nums[j];
                //处于上升
                if(gap > 0)
                    f[i] = max(f[i], g[j] + 1);
                //处于下降
                else if(gap < 0)
                    g[i] = max(g[i], f[j] + 1);
                //相同的情况为1不用处理
            }
            ret = max({ret, f[i], g[i]});
        }
        return ret;
        //时间复杂度O(N ^ 2)
        //空间复杂度O(N)
    }
};

3.最长递增子序列的个数中等

链接最长递增子序列的个数

• 题目描述
  

• 做题步骤

1. 状态表示
   依据前面的经验我们可以定义状态表示dp[i]以i位置为结尾的最长递增子序列个数。

2. 状态转移方程
   要更新当前位置的最长递增子序列个数无非是看接在那几个位置后面长度最大但问题就在于现在只有前面位置的序列个数没有长度所以我们需要再加一个表来记录长度
   (1)count[i]以i位置为结尾的最长递增子序列个数
   (2)len[i]以i位置为结尾的最长递增子序列长度
   
   len[i]前面已经讲过我们分析count[i]
   (1)不接在别人后面最大长度就为1count[i] = 1
   (2)接在[012……i - 1]这些位置后面设0 <= j <= i - 1能保持子序列递增nums[j] < nums[i]就可以接在该位置后面。
   
   从0~i - 1枚举j依据接在那个位置后面的长度进行分析
   ①比原来长度小(len[i] > len[j] + 1)不用管。
   ②比原来长度大(len[i] < len[j] + 1)原来的序列个数无论多少都必须狠狠切割了个数更新为更长的即count[i] = count[j]。
   ③和原来长度一样(len[i] == len[j] + 1)计数增加即count[i] += count[j]。

3. 初始化
   序列长度最小为1全都初始化为1。

4. 填表顺序
   保证填当前状态时所需状态已经计算过填表顺序为从左往右。

5. 返回值
   (1)完成了前面的工作我们知道以每一个位置为结尾的最长递增子序列长度和个数但是并不知道以那几个位置为结尾的序列最长所以我们需要一边dp一边更新最大长度max_length。
   (2)知道了最大长度我们只需要遍历一次count表把长度为max_length的序列统计出来即可。

• 代码实现

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> count(n, 1); //f[i]表示以i位置为结尾的最长子序列个数
        auto len = count; //g[i]表示以i位置为结尾的最长递增子序列长度
        int max_length = len[0];
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    //找到了更加长的
                    if(len[i] < len[j] + 1)
                    {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                    else if(len[i] == len[j] + 1) //长度相同                 
                        count[i] += count[j];               
                }
            }
            max_length = max(max_length, len[i]);
        }
        int ret = 0;    //返回值
        //遍历一次计算最长序列个数
        for(int i = 0; i < n; i++)      
            if(len[i] == max_length)
                ret += count[i];
        return ret;
        //时间复杂度O(N ^ 2)
        //空间复杂度O(N)
    }
};

4.最长数对链中等

链接最长数对链

• 题目描述
  

• 做题步骤

1. 状态表示
   依据前面经验我们定义状态表示dp[i]以i位置为结尾最长数对链长度。

2. 状态转移方程
   这个题目的分析其实和前面的最长递增子序列基本一致。
   (1)不接在别人后面自己玩dp[i] = 1
   (2)接在[012……i - 1]这些位置后面设0 <= j <= i - 1满足数对链要求pairs[j][1] < pairs[i][0]就可以接在该位置后面。
   从0~i - 1枚举j看接在那个位置后面长度最大
   即dp[i] = max(dp[i], dp[j] + 1)

3. 初始化
   长度最小为1全都初始化为1。

4. 填表顺序
   保证填当前状态时所需状态已经计算过填表顺序为从左往右。

5. 返回值
   没法直接确定最长数对链的结尾所以一边dp一边更新最大值。

• 代码实现

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {              
        sort(pairs.begin(), pairs.end());   //先排序
        int n = pairs.size();
        //dp[i]表示以i位置为终点的最长长度
        vector<int> dp(n, 1);
        int ret = 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[i], dp[j] + 1);                         
            ret = max(ret, dp[i]);
        }
        return ret;
        //时间复杂度O(N ^ 2)
        //空间复杂度O(N)
    }
};

5.最长定差子序列中等

链接最长定差子序列

• 题目描述
  

• 做题步骤

1. 状态表示
   依据前面的经验我们定义状态表示dp[i]以下标i位置为结尾的最长等差子序列长度。

2. 状态转移方程
   这个题目最好想的做法就是递增子序列的做法但这样写会超时我们可以分析一下原因
   (1)递增子序列可以接在很多位置的后面。
   (2)等差子序列只能接在固定的位置后面比如(1, 2, 3, 4)difference为1里面的4只能接在3后面其它的判断都是多余的。
   
   那我们就换一种思路还是(1, 2, 3, 4)difference为1这个例子我们在填4位置的时候如果能够直接找到以3(arr[i] - difference)为结尾的最长递增子序列就好了。
   我们可以把元素arr[i]与dp[i]绑定创建一个哈希表hash我们可以直接在这个哈希表中做动态规划那状态转移方程就为
   hash[i] = hash[arr[i] - difference] + 1。

3. 初始化
   在填表的时候如果前置状态不存在我们不单独处理(0加1变成1刚好对应自己一个的情况)。因此我们只需要把第⼀个元素放进哈希表中 hash[arr[0]] = 1即可。

4. 填表顺序
   保证填当前状态时所需状态已经计算过填表顺序为从左往右。

5. 返回值
   不确定最长等差子序列的结尾所以一边dp一边更新最大值。

• 代码实现

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;
        //时间复杂度O(N)
        //空间复杂度O(N)
    }
};

6.最长的斐波那契子序列的长度中等

链接最长的斐波那契子序列的长度

• 题目描述
  

• 做题步骤

1. 状态表示
   依据经验我们可能会定义状态表示为以i位置为结尾的最长斐波那契序列的长度但这样定义有一个致命的问题不知道接在某一个位置后能否构成斐波那契序列。
   一个元素无法确定但如果我们知道斐波那契序列的后两个元素我们就可以推导出前一个元素从而解决前面的问题。
   所以定义一个二维表dp[i][j]以ij位置为后两个元素的最长斐波那契序列的长度。

2. 状态转移方程
   规定 i 比 j 小其中j从[2, n - 1]开始枚举i从[1, j - 1]开始枚举。
   设 nums[i] = b, nums[j] = c 那么这个序列的前⼀个元素就是 a = c - b 我们根据 a 的情况讨论
   (1)a存在设其下标为k并且 a < b这个时候c可以接在以a、b为结尾的斐波那契序列后面则dp[i][j] = dp[k][i] + 1。
   (2)a存在但是 b < a < c这个时候只能b和c两个自己构成dp[i][j] = 2。
   (3)a不存在这个时候只能b和c两个自己构成dp[i][j] = 2。
   
   我们发现在状态转移⽅程中我们需要确定 a 元素的下标。因此我们可以在 dp 之前将所有的「元素 + 下标」绑定在⼀起放到哈希表中。

3. 初始化
   长度最小为2全都初始化为2。

4. 填表顺序
   固定最后一个数枚举倒数第二个数。

5. 返回值
   不确定最长斐波那契子序列的结尾所以一边dp一边更新最大值。

• 代码实现

class Solution {
public:   
    int lenLongestFibSubseq(vector<int>& arr)
    {
        int n = arr.size();
        //i->j
        dp[i][j]表示以i,j为后两个的斐波那契数列最长长度
        vector<vector<int>> dp(n, vector<int>(n, 2));
        unordered_map<int, int> hash;
        for(int i = 0; i < n; i++) hash[arr[i]] = i;

        int ret = 2;
        for (int j = 2; j < n; j++)
        {
            for (int i = 1; i < j; i++)
            {
                int former = arr[j] - arr[i];
                //a b ca < b 并且a存在
                if (former < arr[i] &&  hash.count(former))
                {
                    dp[i][j] = dp[hash[former]][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
        }
        //斐波那契序列最小为3为2的情况返回0
        return ret > 2 ? ret : 0;
        //时间复杂度O(N)
        //空间复杂度O(N ^ 2)
    }
};

7.最长等差序列中等

链接最长等差序列

• 题目描述
  

• 做题步骤

1. 状态表示
   和前面一道题类似只有一个元素无法确定等差序列的样子我们需要有后面两个元素才能确定故定义一个二维表dp[i][j]以ij为后两个元素的最长等差子序列的长度。

2. 状态转移方程
   规定 i 比 j 小设 nums[i] = b, nums[j] = c 那么这个序列的前⼀个元素就是 a = 2 * nums[i] - nums[j] (等差序列的性质捏) 我们根据 a 的情况讨论
   (1)a存在设其下标为k这个时候c可以接在以a、b为结尾的序列后面则dp[i][j] = dp[k][i] + 1。
   (2)a不存在这个时候只能b和c两个自己构成dp[i][j] = 2。
   
   我们发现在状态转移方程中我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标」绑定在⼀起放到哈希表中。对于这个题目哈希表有两种方案
   (1)在dp前就直接放入哈希表可能出现重复的元素这个题目是乱序的前面一题严格递增要记录这些重复元素需要让它们的下标形成一个数组填表前要先遍历数组找到需要的下标时间消耗很大这个方案通过不了。
   (2)只能采取一边dp一边存入哈希表的方式在i位置使用完后存入哈希表中但填表顺序必须固定倒数第二枚举倒数第一不能采用上一题固定倒一枚举倒二的填表方式。我们看这个例子【02444684944】最后一个4固定第一个4为倒数第二时应该去找之前4的下标这里前面是[0,2],没有4意味着这个数不应该在哈希表中但固定倒一枚举倒二的填表方式使得哈希表中是有保存的这个时候就完全乱了

3. 初始化
   长度最小为2全部初始化为2。

4. 填表顺序
   填表顺序为固定倒数第二枚举倒数第一。

5. 返回值
   不确定最长等差序列的结尾所以一边dp一边更新最大值。

• 代码实现

class Solution {
public:
    //dp[i][j]表示以ij为结尾的最长等差数列长度
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash;       
        hash[nums[0]] = 0;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        int ret = 2;
        for (int i = 1; i < n; i++) //倒数第二个
        {
            for (int j = i + 1; j < n; j++)
            {
                int former = 2 * nums[i] - nums[j];
                if (hash.count(former))
                    dp[i][j] = dp[hash[former]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
            hash[nums[i]] = i;
        }
        return ret;
        //时间复杂度ON ^ 2
        //空间复杂度ON ^ 2
    }
};

8.等差数列划分II - 子序列困难

链接等差数列划分II - 子序列

• 题目描述
  

• 做题步骤

1. 状态表示
   和前面一道题一致只有一个元素无法确定等差序列的样子我们需要有后面两个元素才能确定故定义一个二维表dp[i][j]以ij为后两个元素的等差子序列个数。

2. 状态转移方程
   首先这个题目不存在重复的等差子序列只要组成的元素位置不同就视为不同子序列比如[7,7,7,7,7]这个数组等差子序列个数高达16个。
   
   规定 i 比 j 小设 nums[i] = b, nums[j] = c 那么这个序列的前⼀个元素就是 a = 2 * nums[i] - nums[j] 我们根据 a 的情况讨论
   (1)a存在这个时候c可以接在以a、b为结尾的序列后面。设a下标为k这里下标情况就和前面不同了因为可能存在多个a我们需要用一个下标数组来记录不同位置的a下标当k < i时(a在i的前面)dp[i][j] += dp[k][i] + 1这里的+1表示[a,b,c]这一组把满足条件的a全部加起来即可。
   (2)a不存在这个时候只能b和c两个自己构成dp[i][j] = 2。
   
   我们发现在状态转移方程中我们需要确定 a 元素的下标。因此我们可以将所有的「元素 + 下标数组」绑定在⼀起放到哈希表中。

3. 初始化
   无需初始化默认为0。

4. 填表顺序
   填表顺序为固定倒一枚举倒二。

5. 返回值
   定义变量sum一边dp一边累加。

• 代码实现

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        //dp[i][j]表示以i,j为结尾的等差数列个数规定j > i
        //前置可能有存在多个需要一一加起来
        vector<vector<int>> dp(n, vector<int>(n));
        unordered_map<long long, vector<int>> hash; //数据和下标数组绑定
        for(int i = 0; i < n; i++)
            hash[nums[i]].push_back(i);
        int sum = 0;
        for(int j = 2; j < n; j++)
        {
            for(int i = 1; i < j; i++)
            {
                long long former = (long long)nums[i] * 2 - nums[j]; //处理数据溢出
                if(hash.count(former))
                {
                    for(auto k : hash[former])
                    {
                        //former必须在左边
                        if(k < i)
                            dp[i][j] += dp[k][i] + 1; //这里的1表示[a,b,c]单独一组
                        else //当前a下标不满足后面的也一定不满足可以直接跳出
                            break;
                    }      
                }
                sum += dp[i][j];
            }
        }
        return sum;
        //相同数据不多的情况下
        //时间复杂度O(N ^ 2)
        //空间复杂度O(N ^ 2)
    }
};