动态规划设计：最长递增子序列

学会了动态规划的套路：找到了问题的「状态」，明确了 dp 数组/函数的含义，定义了 base case；但是不知道如何确定「选择」，也就是找不到状态转移的关系，依然写不出动态规划解法，怎么办？

不要担心，动态规划的难点本来就在于寻找正确的状态转移方程，本文就借助经典的「最长递增子序列问题」来讲一讲设计动态规划的通用技巧：数学归纳思想。

最长递增子序列（Longest Increasing Subsequence，简写 LIS）是非常经典的一个算法问题，比较容易想到的是动态规划解法，时间复杂度 O(N²)，我们借这个问题来由浅入深讲解如何找状态转移方程，如何写出动态规划解法。比较难想到的是利用二分查找，时间复杂度是 O(NlogN)，我们通过一种简单的纸牌游戏来辅助理解这种巧妙的解法。

力扣第 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]）
输入：nums = [0,1,0,3,2,3] → 输出：4
输入：nums = [7,7,7,7,7,7,7] → 输出：1

注意：「子序列」和「子串」的区别：子串一定是连续的，而子序列不一定是连续的。下面先来设计动态规划算法解决这个问题。

一、动态规划解法

动态规划的核心设计思想是数学归纳法。

比如我们想证明一个数学结论，先假设这个结论在 k < n 时成立，然后根据这个假设，想办法推导证明出 k = n 的时候此结论也成立。如果能够证明出来，那么就说明这个结论对于 k 等于任何数都成立。

类似的，我们设计动态规划算法时，假设 dp[0...i-1] 都已经被算出来了，然后问自己：怎么通过这些结果算出 dp[i]？

直接拿最长递增子序列这个问题举例你就明白了。不过，首先要定义清楚 dp 数组的含义。

alt text

dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。

为什么这样定义呢？这是解决子序列问题的一个套路，读完本章所有动态规划问题，就会发现 dp 数组的定义方法也就那几种。

根据这个定义，我们可以推出 base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。

我们的最终结果（子序列的最大长度）应该是 dp 数组中的最大值。

int res = 0;
for (int i = 0; i < dp.size(); i++) {
    res = max(res, dp[i]);
}
return res;

那么，如何设计算法逻辑来正确计算每个 dp[i] 呢？这里就需要数学归纳的思想：假设我们已经知道了 dp[0..4] 的所有结果，如何通过这些已知结果推出 dp[5]？

根据 dp 数组的定义，想求 dp[5] 的值，就是求以 nums[5] 为结尾的最长递增子序列。

nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到这些子序列末尾，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

nums[5] 前面有哪些元素小于 nums[5]？用 for 循环比较一波就能找出来。以这些元素为结尾的最长递增子序列的长度，就是 dp 数组对应的值。然后我们让 nums[5] 和更长的递增子序列结合，即可得到 dp[5]。

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

类似数学归纳法，你已经可以算出 dp[5] 了，其他的就都可以算出来。整体代码如下：

#include <bits/stdc++.h>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度
    vector<int> dp(nums.size());
    // base case：dp 数组全都初始化为 1
    fill(dp.begin(), dp.end(), 1);
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i < dp.size(); i++) {
        res = max(res, dp[i]);
    }
    return res;
}

至此，这道题就解决了，时间复杂度 O(N²)。总结一下如何找到动态规划的状态转移关系：

明确 dp 数组的定义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
根据 dp 数组的定义，运用数学归纳法的思想，假设 dp[0...i-1] 都已知，想办法求出 dp[i]，一旦这一步完成，整个题目基本就解决了。

如果无法完成这一步，很可能就是 dp 数组的定义不够恰当，需要重新定义 dp 数组的含义；或者可能是 dp 数组存储的信息还不够，不足以推出下一步的答案，需要把 dp 数组扩大成二维数组甚至三维数组。

目前的解法是标准的动态规划，但对最长递增子序列问题来说，这个解法不是最优的，可能无法通过所有测试用例了，下面讲讲更高效的解法。

二、二分查找解法

这个解法的时间复杂度为 O(NlogN)，但正常人基本想不到这种解法（也许玩过某些纸牌游戏的人可以想出来）。大家了解一下就好，正常情况下能够给出动态规划解法就已经很不错了。

其实最长递增子序列和一种叫做 patience game 的纸牌游戏有关，甚至有一种排序方法就叫做 patience sorting（耐心排序）。

简单说：给你一排扑克牌，我们像遍历数组那样从左到右一张一张处理这些扑克牌，最终要把这些牌分成若干堆。 alt text

规则如下：

只能把点数小的牌压到点数比它大或相等的牌上；
如果当前牌点数较大没有可以放置的堆，则新建一个堆，把这张牌放进去；
如果当前牌有多个堆可供选择，则选择最左边的那一堆放置。

比如说上述的扑克牌最终会被分成这样 5 堆（我们认为纸牌 A 的牌面是最大的，纸牌 2 的牌面是最小的）。
alt text

为什么遇到多个可选择堆的时候要放到最左边的堆上呢？因为这样可以保证牌堆顶的牌有序（2, 4, 7, 8, Q）
alt text

按照上述规则执行，可以算出最长递增子序列，牌的堆数就是最长递增子序列的长度 alt text

我们只要把处理扑克牌的过程编程写出来即可。每次处理一张扑克牌需要找一个合适的牌堆顶来放，牌堆顶的牌有序，这就能用到二分查找：用二分查找来搜索当前牌应放置的位置。

#include <bits/stdc++.h>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    vector<int> top(nums.size());
    // 牌堆数初始化为 0
    int piles = 0;
    for (int i = 0; i < nums.size(); i++) {
        // 要处理的扑克牌
        int poker = nums[i];

        // 搜索左侧边界的二分查找
        int left = 0, right = piles;
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        // 没找到合适的牌堆，新建一堆
        if (left == piles) piles++;
        // 把这张牌放到牌堆顶
        top[left] = poker;
    }
    // 牌堆数就是 LIS 长度
    return piles;
}

这个解法确实很难想到，作为思维拓展好了。但动态规划的设计方法应该完全理解：假设之前的答案已知，利用数学归纳的思想正确进行状态的推演转移，最终得到答案。

三、拓展到二维

力扣第 354 题「俄罗斯套娃信封问题」：

给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。

这道题其实是 LIS 的一个变种，相当于在二维平面中找一个最长递增的子序列。

解法比较巧妙：

先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序；
把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。

为什么这样可行？

对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套，所以我们只需要专注高度 h 这个维度能够互相嵌套即可。
两个 w 相同的信封不能相互包含，所以对于宽度 w 相同的信封，对高度 h 进行降序排序，保证二维 LIS 中不存在多个 w 相同的信封。

#include <bits/stdc++.h>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int piles = 0, n = nums.size();
    vector<int> top(n);
    for (int i = 0; i < n; i++) {
        int poker = nums[i];
        int left = 0, right = piles;
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] >= poker)
                right = mid;
            else
                left = mid + 1;
        }
        if (left == piles) piles++;
        top[left] = poker;
    }
    return piles;
}

int maxEnvelopes(vector<vector<int>>& envelopes) {
    int n = envelopes.size();
    // 按宽度升序排列，如果宽度一样，则按高度降序排列
    sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
    });
    // 对高度数组寻找 LIS
    vector<int> height(n);
    for (int i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
}

*学习笔记

暂没有学习笔记，快来抢first blood ！

一、动态规划解法​

二、二分查找解法​

三、拓展到二维​

*学习笔记​

一、动态规划解法

二、二分查找解法

三、拓展到二维

*学习笔记