上N阶楼梯,一次走1个台阶或者2个台阶,共有多少种走法?

假设你需要走n 阶楼梯才能到达楼顶,走楼梯的方式有两种,一次走1个台阶或者一次走2个台阶,问有多少种不同的方法可以走完这n阶楼梯？

先穷举几个n值分析下:

n=1,共1种;

{1}

n=2,共2种;

{1,1},{2}

n=3,共3种

{1,2},

{1,1,1},{2,1}

n=4,共5种

{1,1,2},{2,2},

{1,2,1},{1,1,1,1},{2,1,1}

n=5,共8种

{1,2,2},{1,1,1,2},{2,1,2},

{1,1,2,1},{2,2,1},{1,2,1,1},{1,1,1,1,1},{2,1,1,1}

可以看到,除了n=1和n=2两种情况,是固定的走法外;

走n阶台阶时,可以在n-2个台阶的基础上一次走2个台阶,也可以在n-1个台阶的基础上走1个台阶;也就是f(n)=f(n-1)+f(n-2),这个公式就是著名的斐波那契数列,也叫黄金分割数列、兔子数列.

附上代码:

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

这段代码虽然很好的表达出了斐波那契数列的含义,却不是算法上最优的.明显在计算n时,会计算两次n-2,时间复杂度是O(n^n),效率相当低的算法了.

稍稍优化下,既然在计算f(n-1)时,已经计算了f(n-2),那只要将计算值记录下来,加运算的f(n-2)部分也就不需要二次计算了;

再优化下,在计算f(n)时需要先计算出来f(n-1),这样就需要压栈,这在空间复杂度上也不是最优,既然需要先计算出f(n-1),才能计算出f(n),那按此思路实现下,先计算f(n-1),再计算f(n).

附上代码:

 long climbStairs2(long n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        long n2 = 1;//n-2
        long n1 = 2;//n-1
        long nn = 0;
        for (int i = 3; i <= n; i++) {
            nn = n1 + n2;
            n2 = n1;
            n1 = nn;
        }
        return nn;
    }

总结下,这个实现方式,时间复杂度为O(n),是非常高效的实现方式.

斐波那契数列

下面回到数列本身,之所以斐波那契数列叫做兔子数列,是因为当时提出来的一个兔子假设.

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

简单分析下:

容易得出如下结论:

f(1) =1

f(2)=1

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

在看一下称为黄金分割数列的原因,随着n趋向于无穷大,f(n)/f(n+1)的值越趋近于0.618.

看,你又学会了一种算法!