算法动态规划

最长上升子序列LIS，最经典的单串线性DP状态设计

字数统计: 2k字   |   阅读时长: 8分
, , ,

摘要: 最长上升子序列，动态规划，二分

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一下只要学动态规划就必然涉及的一题：最长上升子序列。它代表了单串上最经典的一类状态设计思路和阶段划分。此外 LIS 问题还有一个很有技巧性的二分算法。

最长上升子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

提示：

1
2
1 <= nums.length <= 2500
-1e4 <= nums[i] <= 1e4

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

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

进阶：

你能将算法的时间复杂度降低到 $O(n \log(n))$ 吗?

算法1：动态规划

LIS 是单串线性 DP 的基础问题，它的状态表示是 $dp[i]$，含义是以 $i$ 结尾的最长上升子序列长度。

阶段划分为子序列的结尾位置。阶段已经可以表示状态，因此状态中没有附加信息维度。

LIS 的这种状态表示和阶段划分方法在单串线性 DP 问题中很常见，完整算法如下：

1
2
3
4
5
6
7
8
9
10
11
dp[i] := [0..i] 上以 i 结尾的最长上升子序列长度

初始化
dp[i] = 1

答案
max(dp[i])

转移
dp[i] = 1 + max(dp[j])
0 <= j < i, nums[j] < nums[i]

$O(N^{2})$

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> dp(n, 1);
        int result = 0;
        for(int i = 0; i <= n - 1; ++i)
        {
            for(int j = 0; j <= i - 1; ++j)
            {
                if(nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

类似于以下的状态转移方程可以用权值线段树或权值树状数组优化，参考文章 权值树状数组优化DP。

LIS

算法2：二分

若 nums 的长度为 $n$，那么最长上升子序列(LIS)的长度是有范围的，最小可能是 1，也就是整个数组是单调不增的，例如下面这个 $n = 5$ 数组，LIS 只能取到 1 的长度。

1
nums1 = [4, 3, 3, 2, 1]

最长可能是 $n$，也就是整个数组就是一个上升的数组，例如下面这个 $n = 5$ 的数组，LIS 就取到了 $n = 5$ 的长度。

1
nums2 = [1, 2, 3, 4, 5]

由于有这样一个范围的限制，我们定义一个数组 vec，vec[i] 表示长度为 i 的上升子序列的最小结尾。

比如上面的 nums2 这个数组，它有若干个长度为 3 的上升子序列，例如 [1, 2, 3], [1, 2, 4], [2, 4, 5] 都是，但是 [1, 2, 3] 这个子序列是其中结尾最小的，那么 vec[3] = 3，类似地，我们可以推出 vec[4] = 4, vec[5] = 5。

nums2 这个 $n = 5$ 数组整个就是上升的，所以 vec[1], vec[2], vec[3], vec[4], vec[5] 都能够取到值。

有的数组不是所有的 vec[1], vec[2], ..., vec[n] 都是能取到值的，比如 nums1，nums[2] 就已经取不到值了，因为它的 LIS 长度也仅仅才 1，长为 2 的上升子序列不存在，vec[2] 自然取不到值。

对于 nums，我们可以发现关于 vec 的以下两个特性：

  • 当某个 1 <= i <= n 可以取到 vec[i] 时，那对于 1 <= j < i，vec[j] 也都能取到值；
  • 当某个 1 <= i <= n 无法取到 vec[i] 时，那对于 i < j <= n，vec[j] 也无法取到值；

因此如果得到 nums 对应的 vec，其中在 1, 2, …, t 上有对应的取值，在 $t+1, t+2, …, n$ 上无法取到值。那么我们就求出了 LIS 的长度 $t$。

那问题就变成了：如何得到 vec。

初始时，vec[1..n] 均标记为一个特殊值，例如 INT_MAX。

然后从 0 到 n - 1 枚举 i，对于 i 我们考察 nums[0..i] 上以 nums[i] 结尾的最长上升子序列，假设其长度为 len，此时考察 vec[len] 有以下是两种情况：

  • vec[len] 为 INT_MAX，说明此前(枚举 0..i-1 时)还没有得到长为 len 的上升子序列。那么就将 vec[len] 改为 nums[i]，表示 nums[0..i] 上长度为 len 的上升子序列的最小结尾为 nums[i]，未来(枚举 i+1..n-1 时)有可能发现某个 i < j < n，以 nums[j] 结尾的最长上升子序列长度也为 len，但是 nums[j] < nums[i]，那么这里的 vec[len] 就会从 nums[i] 更新为 nums[j]。
  • vec[len] 为其它值，那么就看 nums[i] 是否小于 vec[len]，如果小于，就将 vec[len] 更新为num[i]。

当枚举到 i 时，vec[p] 的含义是 nums[0..i-1] 上长度为 p 的上升子序列的最小结尾。现在问题变成了：枚举到 i 时，如何得到 len 是多少。

我们先看 nums[0..i] 上以 nums[i] 结尾且长度为 len 的上升子序列存在需要满足什么条件。如果该子序列存在，那么它是由在 nums[0..i-1] 上的某个长为 len - 1 的上升子序列加上当前的 nums[i] 组成的。因此我们就看此时 vec[len-1]，如果该值 < nums[i]，则说明 nums[0..i-1] 上存在一个长为 len - 1 的上升子序列且其结尾小于 nums[i]，那么nums[0..i] 上以 nums[i] 结尾且长度为 len 的上升子序列也就存在；否则就不存在。

于是问题变成了：满足 vec[len-1] < nums[i] 的最大的 len 是多少。

下面证明 vec 是单调递增的。

反证：因为如果不递增，就存在某个 p1 < p2, vec[p1] >= vec[p2]，对于 nums[0..i-1] 上以 vec[p2] 结尾的上升子序列 arr，arr[0..p1-1] 当然也就是 nums[0..i-1] 上的一个长为 p1 的上升子序列，该序列的结尾是 t = arr[p1-1]，那么 t < vec[p2]。因此 t < vec[p1]，这与 vec 的定义矛盾。$\Box$

因此我们可以二分地在 vec 上找到大于等于 nums[i] 的最小的位置 p，这个 p 就是我要求的 len。

基于以上分析，我们可以写出完整的算法，注意这里的算法中 vec 是从 0 开始的，也就是 vec[p] 表示的是长为 p + 1 的上升子序列最小结尾是 vec[p]，并且只有当枚举到某个 i 时首次发现长为 p + 1 的上升子序列时(枚举 0..i-1 过程中上升子序列长度范围是 1 到 p)，才将 nums[i] 插入到 vec 末尾，也就是 vec[p] = nums[i]。

1
2
3
4
5
6
7
从前往后枚举 i
    vec 始终为一个单调递增的数组，假设我们要把 nums[i] 插入到 vec 中，找到这个插入的位置 p
    如果 p < vec.size():
        则 vec[p] = nums[i]
    否则:
        vec.push_back(nums[i])
vec.size() 为 nums[0..n-1] 上 LIS 长度

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> vec; // vec[i] 是长度为 i 的 LIS 的最小结尾
         for(int i = 0; i < n; ++i)
        {
            // nums[i] 更新到 vec 中
            int p = lower_bound(vec.begin(), vec.end(), nums[i]) - vec.begin(); // lower_bound 得到的是可以插入 nums[i] 的最小的位置
            if((int)vec.size() > p)
                vec[p] = nums[i];
            else
                vec.push_back(nums[i]);
        }
        return (int)vec.size();
    }
};
Share