算法沉淀 —— 动态规划（子序列问题（上））

Dear 丶 2024-04-06 15:58 84阅读 0赞

#### 算法沉淀 —— 动态规划（子序列问题（上）） ####

*  前言
 *  一、最长递增子序列
 *  二、摆动序列
 *  三、 最长递增子序列的个数
 *  四、最长数对链

## 前言 ##

几乎所有的动态规划问题大致可分为以下5个步骤，后续所有问题分析都将基于此

*  1.、状态表示：通常状态表示分为以下两种，其中更是第一种为主。
    
     *  `以i为结尾`，dp\[i\] 表示什么，通常为代求问题（具体依题目而定）
     *  `以i为开始`，dp\[i\]表示什么，通常为代求问题（具体依题目而定）
 *  2、状态转移方程
    
     *  以上述的dp\[i\]意义为根据， 通过`最近一步来分析和划分问题`，由此来得到一个有关dp\[i\]的状态转移方程。
 *  3、dp表创建，初始化
    
     *  动态规划问题中，如果直接使用状态转移方程通常会伴随着`越界访问`等风险，所以一般需要初始化。而初始化最重要的两个注意事项便是：`保证后续结果正确，不受初始值影响；下标的映射关系`。
     *  而`初始化一般分为以下两种：`
        
         *  `直接初始化开头的几个值。`
         *  `一维空间大小+1，下标从1开始；二维增加一行/一列`。
 *  4、填dp表、填表顺序：根据状态转移方程来确定填表顺序。
 *  5、确定返回值

## 一、最长递增子序列 ##

【题目链接】：[300. 最长递增子序列][300.]  
【题目】：

> 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。  
> 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，\[3,6,2,7\] 是数组\[0,3,1,6,2,2,7\] 的子序列。

【示例】：

> 输入：nums = \[10,9,2,5,3,7,101,18\]  
> 输出：4  
> 解释：最长递增子序列是 \[2,3,7,101\]，因此长度为 4 。

【分析】：  
 我们可以定义dp\[i\]表示以i位置为结尾的最长递增子序列。由于每一个数字均可单独构成一个递增子序列，所以我们在创建dp表时，可以将dp表中的值全部初始化为1.

状态转移方程推导:

如果dp\[i\]所表示的递增子序列大于1，此时在i之前一定存在某些元素和nums\[i\]构成递增子序列。而这些元素我们可以用dp\[j\[表示（0 <= j <i）,并且nums\[j\] < nums\[i\]。  
 但j到底在什么位置呢？我们无从而知，需要依次遍历i前的数据。来查找符合要求的最大dp\[j\]。所以状态转移方程为：

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

【其他】：  
 最后只需将dp\[i\]的最终值累加即可！！

【代码编写】：

class Solution {
        
    public:
        int lengthOfLIS(vector<int>& nums) {
        
            int n = nums.size();
            int ret = 1;
            vector<int> dp(n, 1);
            for(int i = 1; i < n; i++)
            {
        
                for(int j = i - 1; j >= 0; j--)
                {
        
                    if(nums[i] > nums[j])
                        dp[i] = max(dp[i], dp[j] + 1);
                }
                ret = max(dp[i], ret);
            }
            return ret;
        }
    };

## 二、摆动序列 ##

【题目链接】：[376. 摆动序列][376.]  
【题目】：

>  如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。  
>  例如， \[1, 7, 4, 9, 2, 5\] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，\[1, 4, 7, 2, 5\] 和 \[1, 7, 4, 5, 5\] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。  
>  子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。  
>  给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

【分析】：  
 我们可以定义dp\[i\]表示以i位置为结尾的最大摆动序列。但我们发现i位置的状态还可以细分为上升和下降。所以我们重新定义:

1.  f\[i\]表示以i位置为结尾，且最后呈 ”上升“ 趋势的最大摆动序列。
2.  g\[i\]表示以i位置为结尾，且最后呈 ”趋势“ 的最大摆动序列。

状态转移方程推导:

1.  f\[i\]：最大摆动序列的长度可能为1，也可能大于1。对于大于1的情况，由于f\[i\]表示最后位置是呈上升趋势的摆动序列，所以`nums[i] > nums[i - 1]`。此时在`i-1`位置一定是呈下降的，即`g[i-1]`。所以状态转移方程如下：

![在这里插入图片描述][2df51a27ebee4038b9dfe9c938e57fe2.png]

1.  对于g\[i\]来说，同理可得状态转移方程如下：  
    ![在这里插入图片描述][0490bff6934144be84c2cab347e689e7.png]

细节处理：

不管是f表还是g表，以i位置为结尾的摆动序列的最小长度一定为1，即nums\[i\]本身。所以我们可以直接将f表和g表中的数据的初始值设为1。后续填表过程中，仅需考虑长度大于1的情况即可！！

【代码编写】：

class Solution {
        
    public:
        int wiggleMaxLength(vector<int>& nums) {
        
            int n = nums.size(), ret = 1;
            vector<int> f(n, 1), g(n, 1);
            for(int i = 1; i < n ; i++)
            {
        
                for(int j = i - 1; j >= 0; j--)
                {
        
                    if(nums[i] > nums[j])
                        f[i] = max(g[j] + 1, f[i]);
                    else if(nums[i] < nums[j])
                        g[i] = max(f[j] + 1, g[i]);
                }
                ret = max(ret, max(f[i], g[i]));
            }
            return ret;
        }
    };

## 三、 最长递增子序列的个数 ##

【题目链接】：[673. 最长递增子序列的个数][673.]  
【题目】：

> 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。  
> 注意 这个数列必须是 严格 递增的。

【示例】：

> 输入: \[1,3,5,4,7\]  
> 输出: 2  
> 解释: 有两个最长递增子序列，分别是 \[1, 3, 4, 7\] 和\[1, 3, 5, 7\]。

【分析】：

我们先定义dp\[i\]表示以i位置为结尾的最长递增子序列的个数。但我们发现dp\[i\]表示两个状态：最长递增、个数。所以我们需要将dp\[i\]状态细分：

1.  我们定义len\[i\]表示以i位置为结尾的最长递增子序列的长度。
2.  定义count\[i\]表示以i位置为结尾的最长递增子序列的个数。

显然len\[i\]、count\[i\]最小为1，即nums\[i\]本身单独构成一个递增子序列。所以我们在创建len表和count表时，我们可以将初始值设为1。  
 如果最大递增子序列长度大于1时，这也意味着在i前就已经存在一个递增子序列（设该子序列以j下标为结尾）。并且满足`nums[i] > nums[j]`，此时该递增子序列（`以j下标结尾，0 <= j < i`）和nums\[i\]构成了一个新的递增子序列。  
 如果最长递增子序列大于1，此时最终结果不仅要保证`nums[i] > nums[j]`，还需保证以j位置结尾的子序列最大（即`len[j]在0 ~ i-1中最大`）。所以我们需要依次遍历`0 ~ i-1`之间len表中的左右值！！

那count\[i\]的值如何更新呢？

我们可以在求len\[i\]的过程中，更新count\[i\]的值。具体如下：

*  如果`len[i] + 1 == len[j]`，此时`count[i] += count[j]`。
 *  如果`len[i] + 1 > len[j]`，此时len\[i\]和count\[i\]的需要重新更新。即`len[i] = len[j] + 1, count[i] = count[j]`
 *  如果`len[i] + 1 < len[j]`，此时count\[j\]是无效次数。我们直接忽略这种情况。

细节处理：  
 通过上述过程我们可以的以i位置为结尾的最大递增序列和次数。所以最终整个数组中，构成的最大递增序列的次数求解可以采用和上述类型的思想。（具体查看代码）

【代码编写】：

class Solution {
        
    public:
        int findNumberOfLIS(vector<int>& nums) {
        
            int n = nums.size();
            vector<int> len(n, 1), count(n, 1);
            int maxlen = 1, maxcount = 1;
            for(int i = 1; i < n; i++)
            {
        
                for(int j = i - 1; j >= 0; j--)
                {
        
                    if(nums[i] > nums[j])
                    {
        
                        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(len[i] == maxlen)
                    maxcount += count[i];
                else if(len[i] >maxlen)
                    maxlen = len[i], maxcount = count[i]; 
            }
            return maxcount;
        }
    };

## 四、最长数对链 ##

【题目链接】：[646. 最长数对链][646.]  
【题目】：

>  给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs\[i\] = \[lefti, righti\] 且 lefti < righti 。  
>  现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = \[c, d\] 才可以跟在 p1 = \[a, b\] 后面。我们用这种形式来构造 数对链 。  
>  找出并返回能够形成的 最长数对链的长度 。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

【分析】：  
 由于题目中明确表示可以任意选择数组中的数来构造数对链。所以我们可以先对数组进行排序。此时我们可以定义dp\[i\[表示以i位置为结尾的最长数对链。

状态转移方程推导分析:

显然dp\[i\]的最小值为1，即\[pair\[i\]\[0\], pair\[i\]\[1\]\]本身构成数对链。  
 如果以i位置为结尾的数对链的长度大于1，此时i位置之前一定存在数对链（`下标设为j，0 <= j <i`）和当前元素构成一个数对链。该情况的出现需满足`pairs[i][0] > pairs[j][1]`。但我们最终的结果是要得到dp\[j\]中的最大值。我们可以直接从后往前遍历，只要查找到第一个满足条件的dp\[j\]即可。（原因在于我们已经对原数组进行排序）  
所以状态转移方程为:

for(int j = i -1; j >= 0; j--)
     {
        
          if(pairs[i][0] > pairs[j][1])
          {
        
              dp[i] = max(dp[i], dp[j] + 1);
              break;
          }
      }

【代码编写】：

class Solution {
        
    public:
        int findLongestChain(vector<vector<int>>& pairs) {
        
            sort(pairs.begin(), pairs.end());
            int n = pairs.size(), ret = 1;
            vector<int> dp(n, 1);
            for(int i = 1; i < n; i++)
            {
        
                for(int j = i -1; j >= 0; j--)
                {
        
                    if(pairs[i][0] > pairs[j][1])
                    {
        
                        dp[i] = max(dp[i], dp[j] + 1);
                        break;
                    }
                }
                ret = max(ret, dp[i]);
            }
            return ret;
        }
    };

[300.]: https://leetcode.cn/problems/longest-increasing-subsequence/description/
[376.]: https://leetcode.cn/problems/wiggle-subsequence/description/
[2df51a27ebee4038b9dfe9c938e57fe2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/24e4dfb7b1f44faaa5e0260d717344e5.png
[0490bff6934144be84c2cab347e689e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a2a6332af72b426585726cb1322247c9.png
[673.]: https://leetcode.cn/problems/number-of-longest-increasing-subsequence/description/
[646.]: https://leetcode.cn/problems/maximum-length-of-pair-chain/description/