完成日期：2021.07.18

Algorithm：300.最长递增子序列

这道题是为了巩固动态规划所做的一道题，也属于动态规划的经典题目。
根据题目的要求，是求出一个序列里最长的递增子序列的长度。其实这道题是进行了简化的，没有让求最长的递增子序列。

分析下题目能够知道，这道题用递归算是最自然、也最容易想到的：

  1. 以原始序列中的每个元素作为子序列的第1个元素
  2. 那么只得到该元素后面所有元素的各种组合得到的最长长度，再+1就可以了
  3. 那么此时问题就变成了剩余的元素中，将所有元素再作为第1个元素，然后再递归的求出其后面所有元素所构成的序列组合中的最长长度，再+1就可以了
  4. 从而构成了递归

用文字写出来还是太抽象，直接看下递归的代码吧：

  1. def L(nums, i):
  2.     '''
  3.     nums: 原始数组
  4.     i   : 当前需要计算的值的索引值
  5.     这里要注意的是递归的值必须是索引i，因为数组里的值是可以重复的，所以
  6.     不能传递数组值
  7.     '''
  8.     if i == len(nums)-1: #到数组末尾了
  9.         return 1
  11.     max_len = 1
  12.     for j in range(i+1, len(nums)):
  13.         if nums[j] > nums[i]:
  14.             max_len = max(max_len, L(nums, j)+1)
  16.     return max_len
  18. def lengthOfLIS(nums):
  19.     max_len = 1
  20.     for i in range(len(nums)):
  21.         max_len = max(max_len, L(nums, i))
  22.     return max_len

代码仔细看的话，还是很简单的，但有一个问题：提交上去后，会报超时。其实要根据70题的经验也知道，这里肯定会超时，因为里面涉及到大量的重复计算。

知道原因了，那么改进也很简单，带上备忘录就好了：

  1. class Solution:
  2.     memo = {}
  3.     def L(self, nums, i):
  4.         if i in self.memo:
  5.             return self.memo[i]
  7.         if i == len(nums)-1:
  8.             return 1
  10.         length = 1
  11.         for j in range(i, len(nums)):
  12.             if nums[j] > nums[i]:
  13.                 length = max(length, self.L(nums, j)+1)
  14.         self.memo[i] = length
  15.         return length
  17.     def lengthOfLIS(self, nums):
  18.         self.memo = {}
  19.         length = 1
  20.         i = 0
  21.         for i in range(i, len(nums)):
  22.             length = max(length, self.L(nums, i))
  23.         return length

这里可以看到每次进行递归的时候，先去备忘录（memo）里查查看是不是已经计算过了，如果计算过了，那么就直接用上回的结果就好了。这样提交后不会超时了，大概4.5秒左右。

在B站上搜了一个该题的讲解，发现这个题还可以倒着想：
image.png
这里以一个5元素的序列为例，那么递归过程如上图：

  • 当求第0个元素的最长长度时，其实就是求出第1、2、3、4个元素为首元素的子序列的最长长度，再+1
  • 当求第1个元素的最长长度时，其实就是求出第2、3、4个元素为首元素的子序列的最长长度，再+1
  • 当求第2个元素的最长长度时，其实就是求出第3、4个元素为首元素的子序列的最长长度，再+1
  • 当求第3个元素的最长长度时，其实就是求出第个元素为首元素的子序列的最长长度，再+1
  • 当求第4个元素的最长长度时，因为只剩这1个元素，所以其长度就是1

这里可以直接看出重复了很多次计算，那我们先后往前求不就好了么！
代码如下：

  1. class Solution:
  2.     def lengthOfLIS(self, nums):
  3.         n = len(nums)
  4.         L = [1] * n
  6.         for i in reversed(range(n)):
  7.             for j in range(i+1, n):
  8.                 if nums[j] > nums[i]:
  9.                     L[i] = max(L[i], L[j]+1)
  11.         return max(L)

代码更短，但需要自己琢磨琢磨，明白了肯定会发出“哦~~”的。
这样的代码提交到力扣平台执行时间可以降到3秒左右。

但这仍然不是终点，老实说当我看到下面这张图的时候，我是崩溃的：
无标题.png
恕我无能，我是真的想不出几十毫秒的答案，我把评论区里最牛逼的答案贴在这儿，以示警醒：

  1. class Solution {
  2.     public int lengthOfLIS(int[] nums) {
  3.         /**
  4.         dp[i]: 所有长度为i+1的递增子序列中, 最小的那个序列尾数.
  5.         由定义知dp数组必然是一个递增数组, 可以用 maxL 来表示最长递增子序列的长度. 
  6.         对数组进行迭代, 依次判断每个数num将其插入dp数组相应的位置:
  7.         1. num > dp[maxL], 表示num比所有已知递增序列的尾数都大, 将num添加入dp
  8.            数组尾部, 并将最长递增序列长度maxL加1
  9.         2. dp[i-1] < num <= dp[i], 只更新相应的dp[i]
  10.         **/
  11.         int maxL = 0;
  12.         int[] dp = new int[nums.length];
  13.         for(int num : nums) {
  14.             // 二分法查找, 也可以调用库函数如binary_search
  15.             int lo = 0, hi = maxL;
  16.             while(lo < hi) {
  17.                 int mid = lo+(hi-lo)/2;
  18.                 if(dp[mid] < num)
  19.                     lo = mid+1;
  20.                 else
  21.                     hi = mid;
  22.             }
  23.             dp[lo] = num;
  24.             if(lo == maxL)
  25.                 maxL++;
  26.         }
  27.         return maxL;
  28.     }
  29. }

这位老哥已经写了注释，但我依然没看懂，后继还要继续加油啊。

Review

无

Tips

本周说一下golang吧，本周花了半天时间将原来用python写的一个图片叠加文字的小程序用golang改写了。说下感受：

  • golang的单代码文件组织方式怎么都比C++高一大截
  • 语法比较简洁，除了接口和指针部分有点迷惑以外，其他的都很容易上手
  • 官方的库非常完整，所有的代码基本都可以直接拿官方库撸
  • 静态打包单一exe，这是golang最大的优点了，也是我学golang的主要动机，想想C++的程序一堆依赖库，还要装不同版本的运行时库就头疼，而golang就容易多了，一句go build main.go，直接就打包好exe了，把exe往别的机器上一扔就能跑，是真的方便！

不过golang也不是这么完美，代码跟python相比还是要啰嗦很多，甚至在改写的时候差点没坚持下来……另外golang中最出名的goroutine在这个小项目里没用上，没能体会到其最强大的地方。

推荐各位有C++基础，但苦于C++弱弱的标准库的同学们上手一下，也许下个项目可能你会想用golang来写哦^-^

Share

无。

这周又懒了，Review又没有，Share的文章也没写（其实上周也不算写）。
自我表达对于个人提升非常有帮助，不论是口头还是笔头，所以下周一定不能再懒了，有想写的题目，先列大纲，周末再扩展开来。