数据结构学习笔记 | 斐波那契数列的两种解法

1. 斐波那契数列

这个数列是意大利数学家斐波那契在《算盘书》里提出的，在数学上是用递归的方式来定义的：

既然是用递归的办法来表示，那么用递归来写代码也就不难了：

int Fibonacci(int n) {
    if (n < 2) return n;

    return Fibonacci(n-1) + Fibonacci(n-2);
}

代码简洁又优雅，我最开始学递归的时候就是学的斐波那契数列的例子，当时就觉得这个思想简直太牛了，代码怎么能写的如此优雅？

不过后来我发现，用递归解斐波那契数列实在不是一个很好的解法，原因如此，来看看斐波那契数列的递归解法的过程，画出来如图：

如果n的取值再大一些，那么重复计算的部分就更多了。

现在看看LeetCode上用递归提交是个什么结果：

用C语言都需要12ms，这个速度实在不忍直视。

既然知道了重复计算问题，那么我们在写代码的时候，如果能够引入一个类似HashMap的结构，保存已经计算过的部分，每次判断一下，就可以节省不少空间，也能节约一些时间。

在之前刷题的时候发现了斐波那契数列还有另一种解法，就是动态规划解法。

引入一个数组dp，dp保存每次计算的结果，这个数字至少前2位应该是确定的：

{0, 1}

再来看看后面的结果：dp2 = f(2) = f(1) + f(0) = dp0 + dp1。以此类推发现dpn = dpn-2 + dpn-2。

这样可以写出这样的代码：

int Fibonacci2(int n) {
    if (n < 2) return n;
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    return dp[n];
}

来看看这个解法在LeetCode的结果：

时间几乎是完美了，这是因为这种动态规划的解法没有重复计算的过程，而且利用的数组，用index搜索的时间复杂度又是O(1)，所以得到的结果非常让人满意。

唯一不如递归的地方就是需要引入一个数组，代码没有递归那么优美。

2. 递归思想

上学的时候老师反反复复的说，递归不是一种算法而是一种思想。《数据结构与算法之美》这本书里讲了一个问座位号的例子，假如你是n排，你只需问一下你的前排他是第几排，然后在他的排数+1就得到了你的n到底是几。如果他也不知道就把问题抛给他的前排。以此类推，到第一排那一定就结束了。

这其实就是一个问题分解的过程，问前排是“递”，前排回答是“归”。

书里给出了递归的三要素：

• 待求解问题可以分解成几个字问题求解
• 待求解问题和子问题之间思路一样，只有规模不同
• 存在递归终止条件

来看看wiki的解释：

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

回到斐波那契数列，F(n)就是可以分解为F(n-1)和F(n-2)解的和，递归终止条件就是n=1和n=0时。

递归除了之前说的重复计算问题之外，还有个问题就是堆栈溢出。排查过Java的Exception日志都知道要去看错误堆栈。这个错误堆栈其实就是每次调用函数时就会把临时变量封装成栈帧压入内存栈，函数执行完之后在弾栈。

而递归的过程，大量的重复调用都会压栈，如果n很大，那么极有可能导致Java里的经典问题StackOverFlow。

3. 动态规划

刚才演示的动态规划解法相比于递归解法，那基本是吊打的。

先从简单的一维动态规划开始研究，以期能搞清楚动态规划的所有套路。

以斐波那契数列为例，如果用递归的办法则会导致一个问题就是重复计算，为了解决重复计算问题，可以引入一个HashMap记录已经计算过的结果。

换种思路，在解题的时候，我记录下每次的结果，然后由当前的结果为依据推出下一步的结果，这样整个推理过程就是动态前进的了。

换句话说，当前步骤的结果就可以用前面步骤的结果推导出来。

换一道题来看看：

先看几个确定的值：

• 如果原地不动那么会有0种走法
• 上一级台阶一定是1种走法
• 上两级台阶一旦是2种走法（1+1 or 2）

所以解集数组最初一定是{0, 1, 2}，这里的数组代表的就是每一个台阶不同的走法。

当n=3时

• 选择跨一步，则应该是1+dp(2)，即1+1+1或者2+1
• 选择夸两步，则应该是2+dp(1)，即1+2

可以推出通项公式：dp[n] = dp[n-1] + dp[n-2]，只需要最后拿到数组最大元素就可以了。

再来一道题验证一下动规的思路，这道题在华为的面试写代码阶段遇到过：

先看看示例1初始化动规数组dp，换做是人计算利润，那么一定会找找看之前哪天的股价最低，所以这个数组应该保存最低的股价，并且dp[0]=0。

这样一来，用眼睛扫一遍股价表，就能算出一个dp数组：{0, 7, 1, 1, 1, 1, 1}。

• i=1开始，如果price[i] > dp[i-1]，即当天的股价大于之前计算出的最低股价，则dp[i]=dp[i-1]，否则dp[i]=price[i]；
• 设置一个max初始值为0用于记录卖出股票的利润，如果当天卖出的利润大于max则max置为dp[i]-price[i]，即当天的利润

杨辉三角的好处是把通项公式基本都写出来了，只是这个图不是很方便看，用表格可以更好的表示出来：

那么动态规划的dp有几个可以确定的点：

• dp是一个二维数组
• dp[i][0] = 1
• if i == j ==> dp[i][j] = 1

除了这些特殊的情况外，dp[i][j] = dp[i-1][j] + dp[i-1][j-1]

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    int** ret = malloc(sizeof(int*) * numRows);
    *returnSize = numRows;
    *returnColumnSizes =  malloc(sizeof(int) * numRows);

    for (int i = 0; i < numRows; i++) {
        ret[i] = malloc(sizeof(int) * (i + 1));
        (*returnColumnSizes)[i] = i + 1;
        ret[i][0] = ret[i][i] = 1;
        for (int j = 1; j < i; j++) {
            ret[i][j] = ret[i-1][j] + ret[i-1][j-1];
        }
    }
    return ret;
}

这个代码有点意思，以前一直写二维数组都是直接申请dp5这样，但是下面的代码里首先申请一维空间，这样代码结束以后，二维数组实际是下图，要么说C语言的程序员首先回去考虑内存的节约，这是个好习惯，Java启动本身JVM就很占空间，加上Java程序员基本不考虑内存，也就很占内存：

解题思路：

• dp是一个维护子数组和的数组
• nums[i] + dp[i-1]的值代表当前数和子数组的和，如果这个值小于当前值，那么子数组应该重新计算

写成代码：

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxSubArray(int* nums, int numsSize){
    if (numsSize == 1) {
        return nums[0];
    }
    int dp[numsSize] ;

    dp[0] = nums[0];
    int maxAns = dp[0];
    for (int i = 1; i < numsSize; i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        maxAns = max(maxAns, dp[i]);
    }
    return maxAns;
}

从这些题目能看出来，要做动态规划，首先要定义清楚dp是保存什么的，然后去推导状态转移公式。

以上的代码有些不是我写出来的，因为LeetCode的编译器和我本地的CLion不知道有什么区别，有些代码CLion可以运行的到了LeetCode就报内存错误。