普通动态规划问题解题四步骤 （涉及最优子结构和重叠子问题）

基于状态压缩的动态规划解题步骤

0-1背包问题

在之前的文章中，我已经给大家介绍过了动态规划的常见类型、解题步骤，以及最重要的重叠子问题和最优子结构性质，从 0-1 背包问题开始，包括今日的最长递增子序列问题都可以视作刷题，找感觉，锻炼你的敏感性！

[LeetCode 300] 给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入输出示例：

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 。

进阶: 你能将算法的时间复杂度降低到 吗?

最长递增子序列（Longest Increasing Subsequence，LIS ），毫无疑问，可以使用动态规划进行求解，具体为何能够用动态规划求解，去看看 普通动态规划问题解题四步骤 这篇文章就是了！不过我这里也会解释奥！

首先从输入输出示例中，你应该注意到：

其一，最长递增子序列中元素并不要求连续，例如：[2,3,7,101] 中的元素在原序列中的元素 2 和 3 在原序列中并不紧挨；

其二，最长递增子序列的组合可能有多个，并不唯一，例如：[1,1,3,2] 的最长递增子序列为 [1,2] 或 [1,3]；

其三，最长递增子序列中的「递增」是「严格递增」，例如：序列[1,1,3,2] 的最长递增子序列中无重复的元素 1，因为 [1,1,2] 不是严格递增

其四，最长递增子序列中元素的相对顺序必须保持和原始序列中的元素相对顺序一致，如下图所示：

此处暂停，回忆回忆动态规划的解题步骤，自己去力扣或者本地测一测，调一调！

最优子结构：设 arr[0 ... n-1] 为输入数组，L(i) 表示以 arr[i] 为结尾的最长递增子序列的长度。

比如：输入 arr[] = {3, 5, 2, 8} ，L(0) 表示以 arr[0] = 3 结尾的最长递增子序列 3 的长度 1 ，L(0) = 1；L(1) 表示以 arr[1] = 5 结尾的最长递增子序列 {3，5} 的长度 2 ，L(1) = 2；L(2) 表示以 arr[2] = 2 结尾的最长递增子序列 {2} 的长度 1 ，即 L(2) = 1；L(3) 表示以 arr[3] = 8 结尾的最长递增子序列 {3，5，8} 的长度 3 ，即 L(3) = 3。

则 L(i) 可以被递归地表示为如下形式：

L(i) = 1 + max( L(j) ) ，其中 且 arr[j] < arr[i] ；比如  L(3) = 1 + L(1) = 3  .

或者 L(i) = 1 ，不存在 arr[j] < arr[i] 的情况；比如 L(2) = 1 ，因为 arr[0] 和 arr[1] 的值均大于 arr[2] 的值。

而最终一个给定数组的 LIS 就是取值最大的 max(L(i)) ，其中 ; 比如，对于数组 arr[] = {3,5,2,8} 而言，其 LIS 的长度为 L(3) = 3 。

由上面的分析可知，对于给定的数组 arr[]， 以 arr[i] 结尾的最长递增子序列的长度等于子问题 arr[j] 的解加 1，其中   且 arr[j] < arr[i] 。也就是说最长递增子序列具有最优子结构性质，可以由子问题的解得到原问题的解。

一图胜千文，我们可以看一下递归树：