用「动态规划」 「模拟」的思想，解决斐波那契数列，文中题目出自 LINE 的面试笔试算法题，难度中等偏上。

Description

Where n is a positive integer, the function f(n) satisfies the follow.

1
2
3

f(0) = 0 
f(1) = 1
f(n) = f(n - 1) + f(n - 2)

Please create a program to find f(n).

Input

Muti datas input until EOF. In every line, input a positive integer n. (1 <= n <= 200)

Output

Please output the result for f(n).

Sample Input 1

1

1

Sample Output 1

1

1

Sample Input 2

1

10

Sample Output 2

1

55

此题目是 LINE 在 2018 年社招移动端岗位放出的笔试题，其中有多道，此道题目是其中的一道。LINE 的考察方式是在白纸上写代码。

另外这题还有一个第二问，请求出 fib(8181) 的答案是多少？

审题

拿到题目的第一件事，当然就是审题了。

乍一看题目很容易就陷入一种这题很简单的误区里，斐波那契数列，一个学校老师只要讲递归就一定会拿出来的例子，快被举烂了，岂不简单？

非也，实际上这是 LINE 的一道难度中等偏上的算法题，如果你大意了，洋洋洒洒写上你的解题答案，你就真的只能被 Out 了。

为什么这么说呢，我们来看回顾一下这道题目的要求：

1. 多组数据输入，直到 EOF。EOF是一个计算机术语，为End Of File的缩写，在操作系统中表示资料源无更多的资料可读取，也就是说你需要允许程序一直输入，直到再没有任何输入为止。
2. n的范围是 [1, 200] 的闭区间，也就是最大允许可以输入 n = 200，这仅仅是第一问，而第二问更是变态的要求你打印出 n = 8181 的结果，是不是感受到了满满的恶意？[手动滑稽]
3. 这是一道白板算法，什么意思呢，也就是说，你不能像 leetcode 的刷题习惯那样给出解法就完了，你需要写出一道完整的可执行的程序出来。

怎么样，在仔细审题之后，是不是发现这道题里充斥着不少陷阱? 其实还是自己太年轻。

分析

下面我们来逐步分析这道题，来看看如何化解它。

当你看见这道题，第一反应肯定是递归，标准教案嘛。那好，我们就先尝试以递归算法来暴力的破解它：

首先，斐波那契数列遵循这样的规律：1、1、2、3、5、8、13、21、34...，也就是说，前两个数相加的结果等于第三个数。

根据题目给出的f(0) = 0, f(1) = 1，我们很容易就能推出，f(2) = 1，因为 0 + 1 = 1 嘛，所以斐波那契的通项公式为：f(n) = f(n - 1) + f(n - 2)，题目也已经在开头提供了该公式，那么用暴力递归的解法就是：

ps: 下文的代码都以 C++ 来演示

1
2
3
4
5
6

int fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

看上去简洁易懂，嗯，也许你还会觉得很完美，这道题 so easy 嘛。

那么问题来了，尝试画一下 n = 20 的递归树，请开始你的表演 👏:

在这个递归树下，想要计算原问题 f(20)，你就得先计算出子问题 f(19) 和 f(18)，要计算 f(19)，你就得计算出 f(18) 和 f(17)，直到计算到 f(2) 和 f(1) 直接返回结果，这是树的左半边，然后你还需要用相同的方式计算出右半边的 f(18)，以此类推。

而递归算法的时间复杂度等于子问题个数乘以解决一个子问题需要的时间，可想而知，这种暴力递归解法是十分低效的。

在这种算法中，子问题个数 = 递归树当中所有节点的总数，本例中 f(20) 的二叉树的节点总数为指数级别，子问题个数为 O(2^n)。

由于只有一个 f(n - 1) + f(n - 2) 加法操作，所以解决一个子问题的时间为 O(1)

综上所述，这个暴力递归算法的时间复杂度为 O(2^n) * O(1) = O(2^n)。

恐怖的指数级别，Boom💥 过后，寸草不生 😱

优化

既然时间复杂度如此之高，我们看看能不能做一下优化，首先需要找到导致算法效率低下的原因：

结合上面的递归树图不难看出，在这个递归过程中，存在着大量的重复运算，比如说你想要计算出 f(19) 的结果，那你就必须先计算出 f(18) 和 f(17) 的结果出来，而你计算 f(18) 的时候，需要计算 f(17) 和 f(16)，这个时候，f(17) 就被重复计算了两次。

再仔细看图，以 f(17) 为根的这棵递归树体量巨大，多算一遍，会耗费巨大的时间，而下面还有更多被重复计算的节点，所以导致这个递归算法的效率极低。

既然是因为重复计算导致的算力低下，那么有没有一个好的方案可以解决这种重复计算呢？回想一下五大经典算法：分治、动态规划、贪心、回溯和分支界定，你会发现这个问题非常适合用动态规划来处理，因为它完全符合动态规划问题的第一个性质：重叠子问题

明确了问题，其实就已经把问题解决了一半。既然重复计算了，那么我们把计算好的结果存在一个查表里备忘，在遇到重复项时，直接读取查表中的结果，也就避免了重复的计算。

也就是说，每次遇到一个子问题时，先去查表里检查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不再耗时去计算了。

这个查表可以由数组构成，也可以选择哈希表 (字典)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int checkSheet(vector<int>& memo, int n) {
    // 未被计算过
    if (n > 0 && memo[n] == 0) 
        memo[n] = checkSheet(memo, n - 1) + 
                  checkSheet(memo, n - 2);
    return memo[n];
}

int fib(int n) {
    if (n < 1) return 0;
    // 查表全初始化为 0
    vector<int> memo(n + 1, 0);
    // 初始化最简情况
    memo[1] = memo[2] = 1;
    return checkSheet(memo, n);
}

现在再来看下之前的这棵递归树：

查表的作用就是把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

再回想一下递归算法的时间复杂度怎么算？子问题个数乘以解决一个子问题需要的时间。

归功于对冗余计算的「剪枝」，优化后的算法中，子问题个数，即图中节点的总数，子问题 = f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。

解决一个子问题的时间，没有任何变化，仍然是只有一个 f(n - 1) + f(n - 2) 加法操作，时间为 O(1)。

所以，本算法的时间复杂度为 O(n) * O(1) = O(n)。和暴力递归的 O(2^n) 比起来，这简直是降维打击 👽。

但这还不是真正意义上的 动态规划，真正的动态规划是「自底向上」的。

递归树是从上向下延伸，是「自顶向下」的。从一个规模较大的原问题，比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案。

而「自底向上」是反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

下面，我们用动态规划的思想「自底向上」用循环迭代来改造一下这个算法：

1
2
3
4
5
6
7

int fib(int n) {
    vector<int> checkSheet(n + 1, 0);
    checkSheet[1] = checkSheet[2] = 1;
    for (int i = 3; i <= n; i++)
        checkSheet[i] = checkSheet[i - 1] + checkSheet[i - 2];
    return checkSheet[n];
}

状态转移方程

「状态转移方程」，实际上就是描述问题结构的数学形式:

斐波那契公式

$$f(n) = \begin{cases} 1, n = 1, 2 \\ f(n - 1) + f(n - 2), n > 2 \end{cases}$$

状态转移方程实际上，就是方程的左半边状态由右半边转移而来，以斐波那契数列公式为例， f(n) 的状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来的，所以叫做状态转移方程。

上面的几种解法中的所有操作，例如 return f(n - 1) + f(n - 2)，checkSheet[i] = checkSheet[i - 1] + checkSheet[i - 2]，以及对查表的初始化操作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出状态转移方程，即这个暴力解。

根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个查表来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

1
2
3
4
5
6
7
8
9
10

int fib(int n) {
    if (n < 2) return n;
    int prev = 0, curr = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

题解

经过上面的分析与算法优化，我们终于可以开始答题了，注意本题的三个要求：

1. 多数据输入，直到 EOF
2. 第一问 n 的范围是闭区间 [1,200]，第二问是指定输出 fib(8181) 的结果
3. 白板算法，需要写出完整的可执行程序

由于需要写出可执行程序，所有引用文件必须得到声明，在此基础上，我们来完成第一条要求，多数据输入:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>

using namespace std;

int fib(int n) {
    if (n < 2) return n;
    int prev = 0, curr = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

int main(int argc, const char * argv[]) {
    int n;
    while (cin>>n) {
        int result = fib(n);
        cout << result << endl;
    }
    
    return 0;
}

这样就结束了吗，恰恰相反，不仅没有结束，本题的陷阱已经悄然展现在你面前，注意第二点要求，这是一个 [1,200] 的闭区间，后面还有第二问，fib(8181)。

这意味着什么呢？意味着你设计的程序需要处理 f(200) 和 f(8181) 这样的边界条件，回想一下上面的那棵树，即使经过剪枝，仍然是庞大的数量计算。

而这会带来什么样的结果呢？答案是 赋值越界。

由于计算中产生的数值结果远远超出了 C/C++ 等语言中整型所能存储的最大范围，会导致整数的赋值越界的问题，程序会在执行过程中发生崩溃，这样设计的程序是肯定无法通过的。

所以，为了规避赋值越界，我们需要对这样的「大数」进行模拟计算，将庞大的整型数值替换为字符串来计算：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include <iostream>
#include <algorithm>

using namespace std;

string findSum(string str1, string str2) {
    // 开始计算之前，确保 str2 的长度更大
    if (str1.length() > str2.length()) {
        swap(str1, str2);
    }
    // 使用一个空字符串存储结果
    string str = "";
  
    // 计算两个字符串的长度
    int n1 = str1.length(), n2 = str2.length();
  
    // 反转两个字符串
    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
  
    int carry = 0;
    for (int i=0; i<n1; i++) {
        // 计算当前数字的总和并进位
        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
  
        // 计算下一步的进位
        carry = sum/10;
    }
    // 加上 str2 的其余位数
    for (int i=n1; i<n2; i++) {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }
    // 加入剩余进位
    if (carry) {
        str.push_back(carry+'0');
    }
    // 反向结果字符串
    reverse(str.begin(), str.end());
  
    return str;
}

string fib(int n) {
    if (n < 2) return to_string(n);
    string prev = "0", curr = "1";
    for (int i = 0; i < n - 1; i++) {
        string sum = findSum(prev, curr);
        prev = curr;
        curr = sum;
    }
    return curr;
}

int main(int argc, const char * argv[]) {
    int n;
    while (cin>>n) {
        string result = fib(n);
        cout << result << endl;
    }
    
    return 0;
}

完美解决了三点要求，至此，题解结束 👊。

题外话

当然，你可以使用 Python 或者 Java 这类拥有 BigInteger的语言来写这道题目，因为并没有语言限制，但是这样就失去了题目本身考察的意义。

———— 2019.11.14 更新 ————

Swift 最新的 Future plans 中，也准备支持支持超高精度大数了，Swift 将支持大于 64 位的固定宽度整数类型。

Swift 开源社区宣布了一项新的生态系统项目：Swift Numerics, Swift Numerics 将为 Swift 中的数值计算提供构建模块，其目的是为了填补现有标准库当中的 API 空白，就比如对超高精度大数的支持。

详情见：
Fixed-width integer types
Swift Numerics

————- 更新内容结束 ————-

下面是 Python 版本的题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def fib(n):
    if n < 2:
        return n
    a,b = 0,1
    for i in range(n):
        sum = a + b
        a,b = b,sum
    return a

#多组测试数据，处理到文件结束。
while True:
    try:
        n = int(input())
        r = fib(n)
        print(r)
    except EOFError:
        break

参考

递归详解
动态规划详解