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

300. 最长递增子序列

354. 俄罗斯套娃信封问题

前文详细讲解了「动态规划解题套路框架」详情可见动态规划解题套路框架

在这篇文章中首先介绍动态规划的三个特点，即：存在「重叠子问题」、具备「最优子结构」、正确的「状态转移方程」

其次给出了一个动态规划的框架，即：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

最长递增子序列

题目详情可见最长递增子序列

下面我们结合「三个特点」和「动态规划框架」来详细分析这个问题

分析：原问题「最长严格递增子序列的长度」，我们把原问题稍微转换一下，「以nums[i]结尾的最长严格递增子序列的长度」

对于一个长度为n的数组来说，如果我们要计算以nums[n - 1]结尾的最长严格递增子序列的长度，我们只需要在以nums[0]...nums[n - 2]结尾的最长严格递增子序列中找到尾数比nums[n - 1]小的子序列，然后在该数量上 +1 即可，最后选出最大值即为以nums[n - 1]结尾的最长严格递增子序列的长度

举个简单的例子，对于：nums = {10, 9, 2, 5, 3, 7, 101, 18}的数组来说，先看下图：

假设0 - 6的结果都已经计算出来了，现在需要计算以18结尾的最长递增序列长度。按照我们上面的分析，18和nums[0]...nums[6]相比，只有10, 9, 2, 5, 3, 7比18小，所以18可以接在比它小的元素后面形成长度 +1 的递增子序列，我们只需要在长度 +1 的递增子序列中挑选出最长的即为以18结尾的最长递增子序列的长度

有了上述的分析，我们现在把「动态规划框架」中四个要素明确一下：

明确 base case：显然是每个元素自身单独为一个子序列时，直接返回 1
明确「状态」：原问题和子问题中会发生变化的变量。由于当前元素n的值需要根据之前所有元素[0, n-1]的值来确定，所以区间会不断地向 base case 靠近，所以唯一的「状态」就是数组区间
明确「选择」：导致「状态」产生变化的行为。数组区间为什么变化呢？因为在选择该区间内符合要求的最长递增子序列长度，每选择一个符合的长度，数组区间就会相应的减少。所以说「数组区间内所有以nums[i]结尾的最长递增序列长度」就是「选择」(每次都在集合中选择符合要求的长度)
明确 dp 数组/函数的定义：这里采用自底向上的解法，所以会有一个递推的dp数组，一般来说数组的下标就是状态转移中会变化的量，即：「状态-区间长度」；数组的值就是以nums[i]结尾的最长递增序列的长度

根据上面的分析，我们可以很容易的写出完整代码：


x
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    // 记录最终答案，res 为 dp[] 中的最大值
    int res = 0;
    // base case
    Arrays.fill(dp, 1);
    // 自底向上依次计算 dp[i] 的值
    for (int i = 0; i < nums.length; i++) {
        // 根据区间 [0, i) 来确定 dp[i] 的值
        for (int j = 0; j < i; j++) {
            // 说明 nums[i] 可以接到以 nums[j] 结尾的子序列上
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        // 完成 dp[i] 的计算
        // 更新 res
        res = Math.max(res, dp[i]);
    }
    return res;
}

根据上面的代码，很容易给出这个问题的「状态转移方程」：

\begin{matrix} d p (n) = {\begin{matrix} 1 & , n = 0 \\ max {d p (n - i) + 1 | 0 \leq i < n & & n u m s [n] > n u m s [i]} & , n > 0 \end{matrix} \end{matrix}

至此我们已经分析完了，但是我们并没有说这个问题是否存在「重叠子问题」、具备「最优子结构」，我们都用动规完整写出来了，你说有没有呢！！！哈哈哈哈哈

不过呢，我还是准备从这两个方面分析一下

先来说说是否具备「最优子结构」？思考一个很简单的问题，如果我们计算出了{1, 4, 3, 4}的最优解，现在我们增加一个数字5，我们之前计算的结果是否可以重用！？根据上面的分析，显然是可以的，因为数字之间不存在相互制约，所以这个问题是具备「最优子结构」的

然后再来说说是否存在「重叠子问题」？关于这个问题，最简单明了的方法就是画出递归树。不说废话，直接看图叭！

$O(N^2)$ 。总结一下如何找到动态规划的状态转移关系：

明确dp数组的定义。这一步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤

根据dp数组的定义，运用数学归纳法的思想，假设dp[0...i-1]都已知，想办法求出dp[i]，一旦这一步完成，整个题目基本就解决了

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

优化：利用二分搜索

二分搜索详情可见二分搜索

这种方法就不展开赘述了，有兴趣的可自行搜索，反正自己是想不到这种方法滴滴滴！！！


x
public int lengthOfLIS(int[] nums) {
    // 每堆顶部扑克
    int[] top = new int[nums.length];
    // 扑克堆的数量
    int piles = 0;
    for (int i = 0; i < nums.length; i++) {
        // 要处理的当前扑克
        int poker = nums[i];
        // 注意区间开闭 [left, right)
        int left = 0, right = piles;
        while (left < right) {
            int mid = left - (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;
    }
    return piles;
}

俄罗斯套娃信封问题

题目详情可见俄罗斯套娃信封问题

这就是一个二维的最长递增子序列问题！

第一版思路：先对信封先按照宽度递增排序，如果宽度相等，再按照高度递增排列

注意：这里对宽和高都是递增排序

第二版思路：先对信封先按照宽度递增排序，如果宽度相等，再按照高度递减排列

这样做的一个好处就是，我们可以只用根据高度来计算最长递增子序列。如图：

代码如下：


x
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (o1, o2) -> {
        if (o1[0] != o2[0]) {
            return o1[0] - o2[0];
        } else {
            return o2[1] - o1[1];
        }
    });
    int[] dp = new int[envelopes.length];
    Arrays.fill(dp, 1);
    int res = 0;
    for (int i = 0; i < envelopes.length; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[i][1] > envelopes[j][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

很遗憾，超时了！！😭😭😭

第三版思路：利用二分搜索


xxxxxxxxxx
public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (o1, o2) -> {
        if (o1[0] != o2[0]) {
            return o1[0] - o2[0];
        } else {
            return o2[1] - o1[1];
        }
    });
    int n = envelopes.length;
    int[] top = new int[n];
    int piles = 0;
    for (int i = 0; i < n; i++) {
        int poker = envelopes[i][1];
        int left = 0, right = piles;
        while (left < right) {
            int mid = left - (left - right) / 2;
            if (top[mid] < poker) left = mid + 1;
            else if (top[mid] > poker) right = mid;
            else right = mid;
        }
        if (left == piles) piles++;
        top[left] = poker;
    }
    return piles;
}