日期: 2020 年 2 月 15 日

最长递增子序列（Longest Increasing Subsequence）

最长递增子序列的解法，可以转化为 求最长公共子序列，也就是生成从目标序列从小到大排序之后的新序列，然后计算原始序列与新序列的 最长公共子序列。但是遇到重复数字的时候，会出现问题。也就是这个解法只能解决无重复数字的最长递增子序列。

另外需要注意的就是 最长公共子串（Longest Common Substring）与 最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

整个的求解过程其实很好理解：

  • 假定要计算的序列为 K = {K1,K2,K3,……,Kn,Kn+1,……,Km}
  • 初始化计数数组 N = {N1,N2,N3,……,Nn,Nn+1,……,Nm} ，（计数数组跟序列的长度相同，Kn 的最长递增子序列长度计数对应于 Nn）用来记录最长递增子序列的长度，每个项的初始化值都设置为 1 （即使最小的项，项本身也算一个长度，因此最小的长度是 1）
  • 必须从头部(K1)开始遍历
  • 当计算 Kn 结尾的最长递增子序列的时候，只要遍历序列 K 的前 [0 ~ n-1] 个项，找到数值 小于(或者小于等于） Kn （必须遍历，Kn 之前的最长递增子序列不一定是 Kn-1 对应的 Nn-1 ），并且在计数数组 N 中对应的计数最大的项 Ni ，然后 Nn = Ni + 1 。

本方法的时间复杂度是 O(n2)

例子：

设数组 K = { 2， 5， 1， 5， 4， 5 }  那么求最长递增子序列的代码如下：

第二个测试用例的数据如下：

涉及到的面试题目如下类型：

 
梅花桩问题

合唱队问题

合唱队问题其实是 求最长递增子序列 与 最长递减子序列 的 和 最大。

最长递减子序列的求法其实就是把原始序列反序，然后 求最长递增子序列 然后把最后的结果反序即可。

代码如下：

解法介绍

参考链接

兔子生兔子问题详解(斐波那契数列)

有一只兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

这个问题可能我比较笨，看大多数解释都是一句话，f(n) = f(n-1) + f(n-2)，但是总有点想不明白这个。列了个表格才看清楚咋回事。

月份 1 2 3 4 5 6 7
兔子总数 1 1 2 3 5 8 13
具有生育能力兔子 0 0 1 1 2 3 5

如果这个月是第n个月，那要求这个月兔子的总数，其实就是上个月的兔子总数加上新生出来的兔子。也就是f(n) = f(n-1) + x。这个x是比较难理解的地方。那这个月到底新生出来多少兔子呢？这就是求这个月已经有生育能力的兔子是多少，上上个月所有的兔子就是这个月所有的有生育能力的兔子，这里可以结合表格推一推就很好理解了。所以x就是f(n-2)。

因此可以得到递推f(n) = f(n-1) + f(n-2)。

其实比较简单的问题，不过自己光凭笨脑子想，突然没想明白，记一下这个思考过程。

还有就是牛客网上的高赞答案详解：

有人是以a表示一个月的兔子，b表示两个月的兔子，c表示三个月的兔子（原文这么注释的），我因为这个注释半天没看懂，后来明白了，c意思是已经成熟的兔子，也就是表示3个月及以上的兔子，也就是说c表示能生兔子的兔子。

那就可以以月份循环，每到达新的一个月，b都会成熟，所以c+=b，c就更新了，仍然表示所有成熟了的兔子，b怎么更新呢？b其实就是上个月那些成熟度是1个月的兔子，所以再更新b，用b=a；a呢？a就是现在更新后的c，因为更新后的c表示这个月成熟了的兔子，那这些兔子都会生一只新的兔子，新兔子就是成熟度为1个月的，所以用a=c。这样现在这个月的兔子总数就是a+b+c。

这是我自己没找到注释，自己总结出来的答案详解，这个方法比递归复杂度低，空间占用更是比用数组先去存要少很多。

参考链接