序列DP | 最长递增子序列

缺乏、安全感 2023-07-20 05:50 15阅读 0赞

> 首先一定要分清楚 **子串** 与 **子序列** 的概念：两者都是从某一序列种从左向右找出一定元素组成的，但子串是一定要连续的，而子序列不需要。例如：串 abcde 的字串可以为 abc、cde 等，子序列可以为 abc、ade、ace 。

--------------------

> **最长递增子序列问题(LIS)**：给定一个有 n 个元素的序列 a\[ \]，求出其递增子序列的最大长度。

短短的题目透露出了很大的恶意啊...这个问题我想了很久，也参考了很多资料，回味了很多遍后终于算是掌握了，今天把笔记记上，一面下次又忘记了很难拾起来。除了十分暴力又费时的枚举算法外，下面总结了两种实现方法：

--------------------

### 1、动态规划 —— 时间复杂度![O(n^2)][O_n_2] ###

通过分析，对于一个递增子序列 s，元素 e 是否能加入到序列的末端使得其长度加一，要看 e 是否大于序列 s 的最后一个元素。故，对本问题讨论的递增序列来说，序列的最末元素是至关重要的。

那么思路来了：dp\[ i \] = 以元素 a\[ i \] 结尾的最长子序列长度，那么其**状态转移方程如下：**

![\\bg\_white dp\[i\] = max\_\{0\\leq k< i , a\[k\] <a\[i\]\}(dp\[ k \] ) + 1][bg_white dp_i_ _ max_0_leq k_ i _ a_k_ _a_i_dp_ k _ _ _ 1]

**初始情况：**将dp数组全都赋初值1

那么最终的答案就是 ![\\bg\_white LIS = max\_\{1\\leq i\\leq n\}(dp\[i\])][bg_white LIS _ max_1_leq i_leq n_dp_i]

--------------------

**代码实现：**

#include <algorithm>
    #include <climits>
    #define MAXN 100000
    using namespace std;
    
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            int len = 0, dp[MAXN];
            /* 将dp初值全设置为1 */
            for(int i = 0; i < MAXN; i++)
                dp[i] = 1;
            for(int i = 0; i < nums.size(); i++) {
                for(int j = 0; j < i; j++)
                    if(nums[j] < nums[i]) 
                        dp[i] = max(dp[i], dp[j] + 1);
                len = max(len, dp[i]);  //更新最大长度
            }
            return len;
        }
    };

--------------------

### 2、动态规划 + 二分查找 —— 时间复杂度![O(nlogn)][O_nlogn] ###

这个方法比上面快，但是也相对难理解一些：

首先要弄明白：其实对于一个子序列，我们希望它的最末元素越小越好，这样子才有机会变得更长。那么其实在讨论时，**对于等长度的递增子序列中，我们只需要在其中挑选 最末元素最小的 那个序列继续讨论即可。**比如说：序列 "1 3 2 6 9"，我在讨论前 3 项的时候，有两个长度为 2 的递增子序列："1 3"、"1 2"，那么接下来应该在序列 "1 2" 上进行延续，"1 3" 序列完全可以被其更佳地替换掉。

--------------------

那么思路就来了： 取用一个数组 **tail\[ i \] ：长度为 i** 的递增子序列的**最小的最末元素**（有点绕，看看例子更好理解），最终 tail 开辟了多长，LIS就是多长。且 **tail 数组一定是一个递增的序列**！最初情况：tail\[ 1 \] = a\[ 0 \]，len = 1。

具体算法如下，依次遍历数组 a\[ \] 中的元素：

*  若a\[ i \] >= tail\[ len \] ：既然此元素比我们记录的当前最长子序列的最末元素还要大，那么可以**增长我们的最长子序列**：len ++, tail\[ len \] =  a\[ i \]
 *  否则：那么就不能增长子序列长度，但可以看是否可以**更新前面稍微短一些的子序列的最末元素的最小值**。用**二分法**(tail数组是递增的)找到 下标 k 满足![tail\[k\] < a\[i\] < tail\[k+1\]][tail_k_ _ a_i_ _ tail_k_1]，然后赋值 tail\[k +1\] = a\[ i \]。

下面看一个示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

--------------------

注意：

1.  最终 tail 开辟的长度len即为答案，不过tail中留下的序列不一定是我们的最长递增子序列哦，只能说这个方法能算出长度，但是无法给出对应的答案序列。
2.  二分查找的时间复杂度为 ![O(logn)][O_logn]

--------------------

**代码实现：**

#include <algorithm>
    #include <climits>
    #define MAXN 100000
    using namespace std;
    
    class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            /* 防止nums为空的情况导致RE */
            if(nums.size() == 0)
                return 0;
            int tail[MAXN] = {0}, len = 1; 
            tail[1] = nums[0];
            for(int i = 1; i < nums.size(); i++) {
                if(nums[i] > tail[len])
                    tail[++len] = nums[i];
                else {
                    int index = Find(tail, 0, len, nums[i]); //二分查找
                    tail[index] = nums[i];  //赋值
                }    
            }
            return len;
        }
        /* 在数组a[l..r]中找到 a[k - 1] < temp <= a[k] 
           返回k */
        int Find(int a[], int l, int r, int temp) {
            if(r - l == 1)
                return r;
            int mid = (l + r) / 2;
    
    
            if(temp == a[mid])
                return mid;
            else if(temp < a[mid])
                return Find(a, l, mid, temp);
            else 
                return Find(a, mid, r, temp);    
        }
    };

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]

[O_n_2]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28n%5E2%29
[bg_white dp_i_ _ max_0_leq k_ i _ a_k_ _a_i_dp_ k _ _ _ 1]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%20%3D%20max_%7B0%5Cleq%20k%3C%20i%20%2C%20a%5Bk%5D%20%3Ca%5Bi%5D%7D%28dp%5B%20k%20%5D%20%29%20&plus;%201
[bg_white LIS _ max_1_leq i_leq n_dp_i]: https://private.codecogs.com/gif.latex?%5Cbg_white%20LIS%20%3D%20max_%7B1%5Cleq%20i%5Cleq%20n%7D%28dp%5Bi%5D%29
[O_nlogn]: https://private.codecogs.com/gif.latex?%5Cbg_white%20O%28nlogn%29
[tail_k_ _ a_i_ _ tail_k_1]: https://private.codecogs.com/gif.latex?tail%5Bk%5D%20%3C%20a%5Bi%5D%20%3C%20tail%5Bk&plus;1%5D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/38531a3727b0485ba8f9bfa475880e3b.png
[O_logn]: https://private.codecogs.com/gif.latex?O%28logn%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70 1]: /images/20230528/7b7b193d6a00446b999f4fdeb4d10ab9.png