三步问题介绍

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

方法1：递归

基线条件：

没有台阶，0种上楼梯的方式。1个台阶，1种上楼梯的方式。2个台阶，2种上楼梯的方式。3个台阶，4种上楼梯的方式。

子问题分析：

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

在第n-1处往上迈1步。在第n-2处往上迈2步。在第n-3处往上迈3步。

把这三种方式的路径数加起来就是走到第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)