动态规划经典题之最长上升子序列

最长上升子序列（LIS）

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

明确两个概念

要求最长上升子序列，必须明确两个概念，即什么是子序列和什么是单调递增。

什么是子序列？

子序列是指原序列中的一个连续的子序列还是可以间隔的只要保证元素之间相对位置不变就可以的子序列？

什么是单调递增？

单调递增一般是指序列的后一个数比前一个数大，是否还需要考虑后一个数跟前一个数相等这种情况？

题目：最长递增子序列

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

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

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]

输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

解题思路

1

绝对递增

从题目中的“最长严格上升子序列”可以看出，题目要求的是绝对上升子序列，例如 [1, 2, 2, 3, 4]，这样的子序列就不符合题目要求。

2

非连续

从题目中的示例 nums = [10,9,2,5,3,7,101,18] 的解释可以看出本题的子序列不要求连续，只要保证元素前后顺序一致即可。

思路一（暴力法）：可以先找到所有的子序列，然后再判断这些子序列是否为递增子序列，最后再在这些递增子序列中找出最长的即可。

序列中的每个元素要么加入子序列中，要么不加入，即每个元素都有两种选择，如果有 n 个元素，就有 2^n 种选择。因此对所有子序列进行判断，其时间复杂度为 O(2^n)，对于每个子序列还需要判断其是否为递增子序列，因此还需要乘 n，所有该解法的时间复杂度为 O(n * 2^n)。

思路二（动态规划）：涉及到求最优解的问题，都可以考虑用动态规划方法去解。时间复杂度为O(n^2)。

1、定义状态

LIS(i) 表示以第 i 个元素结尾的最长递增子序列的长度。

由于前面已经提到每个元素可以选择加入子序列也可以选择不加入，这里关注元素选择加入子序列，会发生什么。当该元素被选择加入子序列，该元素的位置是不固定的，不利于分析问题，因此需要给该元素找一个特殊的位置，由于每个子序列都有一个元素结尾，因此将选取的该元素作为子序列的结尾，即 nums[i] 必须选取。

2、状态转移方程

假设选择将元素nums[i]加入到当前最长递增子序列LIS[j]（以nums[j]结尾的）中并以nums[i]结尾，可以获取比当前更长的递增子序列LIS[i].

LIS[i] = max(1+LIS[j])，其中 j < i 且 nums[j] < nums[i]。

举栗：求数组 [1, 4, 2, 3] 的最长递增子序列。

初始化，每个元素只考虑自己不考虑其它元素，以自己结尾的子序列都是长度为 1 的上升子序列。

求出以前面元素结尾的最长递增子序列长度之后，即可求出以后面元素结尾的最长递增子序列的长度。

如上图示，以 1 结尾的最长递增子序列的长度还是 1；对于 4 来说 4 > 1，所以可以凑成当前的最长递增子序列且其长度为以 1 结尾的最长递增子序列的长度加 1 等于 2；同理对 2 来说，其前面的两个元素是 1 和 4，由于 4 > 2，不能与 2 凑成当前最长递增子序列，但是 1 < 2，因此能与 2 凑成当前最长递增子序列且长度为 1 + 1 = 2；同理对 3 来说，以 3 结尾的最长递增子序列的长度为以 2 结尾的最长递增子序列的长度加 1 等于 3。

Show me the Code

// c++
int lengthOfLIS(vector<int>& nums) {
  if (nums.size() == 0) {
    return 0;
  }

  /* res[i] 表示以 nums[i] 结尾的最长递增子序列的长度 */
  vector<int> res(nums.size(), 1);
  for (int i = 1; i < nums.size(); i++) {
    for (int j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        res[i] = max(res[i], 1 + res[j]);
      }
    }
  }

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