斐波那契数列证明（三步问题算法解答）

三步问题介绍

有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。

方法1：递归

基线条件：

子问题分析：

那么小孩有多少种方法走到第n阶台阶呢？我们可以通过以下三种方式走到第n阶台阶。

把这三种方式的路径数加起来就是走到第n阶台阶的所有方式。

递归实现：

public int countRecursion(int n){
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;
    return countRecursion(n-1) + countRecursion(n-2) + countRecursion(n-3);
}

时间复杂度: O(3ⁿ)

时间复杂度的证明可参考“斐波那契数列算法”一文。

方法2：自上而下的动态规划

在方法1的递归实现中，我们可以看到很多重复的节点计算。计算第n阶台阶时，会计算第(n-1)阶台阶、第(n-2)阶台阶和第(n-3)阶台阶；计算第(n-1)阶台阶时，会计算第(n-2)阶台阶、第(n-3)阶台阶和第(n-4)阶台阶。

为什么要重复地计算第(n-2)阶台阶和第(n-3)阶台阶......? 如果我们把计算过的第i阶台阶的值缓存起来，下次遇到计算过的值直接从缓存里取，时间复杂度将从指数级降到O(n)。

自上而下的动态规划实现：

public int countDynamicUpDown(int n){
    int[] ways = new int[n+1];
    Arrays.fill(ways,-1);
    return count(n, ways);
}

private int count(int n, int[] ways){
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;
    if(ways[n] == -1){
        ways[n] = count(n-1, ways) + count(n-2, ways) + count(n-3, ways);
    }
    return ways[n];
}

时间复杂度: O(n)

方法3：自下而上的动态规划

从基线条件中已经知道n=1、n=2和n=3时的值，通过利用这些已知的值，我们可以计算出n=4时的值。接着我们可以根据已知的值计算出n=5、n=6......的值。

自下而上的动态规划实现：

public int countDynamicDownUp(int n){
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;

    //Set base case
    int[] counts = new int[n+1];
    counts[0] = 0;
    counts[1] = 1;
    counts[2] = 2;
    counts[3] = 4;

    //Count from base case
    for (int i = 4; i <= n; i++) {
        counts[i] = counts[i-1] + counts[i-2] +counts[i-3];
    }

    return counts[n];
}

时间复杂度: O(n)

空间复杂度: O(n)

方法4：空间优化方法3

观察方法3，你会发现counts[i]只会被使用3次：

counts[i+1] = counts[i] + counts[i-1] + counts[i-2]

counts[i+2] = counts[i+1] + counts[i] + counts[i-1]

counts[i+3] = counts[i+2] + counts[i+1] + counts[i]

我们可以用变量来存储中间值，不需要使用额外的counts数组来存储中间值。

空间优化方法实现：

public int countDynamicSpaceOpt(int n){
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;

    //Set base case
    int a = 1;
    int b = 2;
    int c = 4;

    //Count from base case
    for (int i = 4; i < n; i++) {
        int d = a + b + c;
        a = b;
        b = c;
        c = d;
    }

    return a + b + c;
}

时间复杂度: O(n)

空间复杂度: O(1)