斐波那契数列应该是很简单的一道题目，但是我曾经在面试中没有做出来。

有时候面试官不会直接说写出斐波那契数列算法，而是会包装一下，比如我之前遇到的题目是这样的：

题目：跳台阶一次可以上1个台阶，也可以一次上两个台阶，如果一共有N个台阶，一共有多少种走法？

可以参考：走楼梯问题

我们考虑，我们是如何跳到N这个台阶的，一共有两种方式，一种是从N-1台阶跳一个台阶，另外一种是从 N-2跳2个台阶，所以：

F(n) = F(n-1) + F(n-2) 并且 F(1)=1, F(2) = 2 。

容易看出，其实这就是一个斐波那契数列。

但如果写这样的代码，是不会通过面试的要求的，因为这里会有大量的重复计算。

消除重复计算的方法：备忘录和DP数组

备忘录：也就是每次计算完成之后，存下来，下次计算时，先查备忘录，有计算结果就直接使用。一般使用数组或者是哈希表（字典）来作为备忘录。且备忘录是自顶向下的，比如要计算F(10)，则要先计算F(9)和F(8)...

DP数组：这里用动态规划的DP数组，自底向上的计算，填充dp数组的值，最后dp数组就是一个完整的备忘录

这里以DP数组的形式编写题解：

Java版本：

    private static int getFibNumber1(int n) {
        if (n <= 0) return -1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

但是这里使用的一个dp数组，空间复杂度是O(n)

如果面试官要求空间复杂度为O(1)，那么就需要使用到 状态压缩，即只记录必要的数据。

  private static int getFibNumber2(int n) {
        if (n <= 0) return -1;
        if (n == 1) return 1;
        if (n == 2) return 2;

        int pre = 1, cur = 2;
        for (int i = 3; i <= n; i++) {
            int sum = pre + cur;
            pre = cur;
            cur = sum;
        }
        return cur;
    }

kotlin版本：

fun getFib(n: Int): Int = when (n) {
    1 -> 1
    2 -> 2
    else -> {
        var pre = 1
        var cur = 2
        for (i in 3..n) {
            val sum = pre + cur
            pre = cur
            cur = sum
        }
        cur
    }
}

本系列的完整代码以及测试用例：https://github.com/chenyucheng97/labuladongCodes