上台阶问题

栗子

有一段楼梯台阶有15级台阶，以小明的脚力一步最多只能跨3级，请问小明登上这段楼梯有多少种不同的走法?

类似用递归求斐波那契数列。

• 一个阶梯的时候 只有一种方法 1
• 两个阶梯的时候 有两种方法 11，2
• 三个阶梯的时候 有四种方法 111，12，21，3
• 四个阶梯的时候 有七种方法 1111，112， 121， 211 ，22 ， 13 ， 31

可以观察到f(4) = f(3) + f(2) + f(1)即f(n) = f(n-1) + f(n-2) + f(n-3) 依此写出下面的code

#Python
def stairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4

    return stairs(n-1) + stairs(n-2) + stairs(n-3)

print fib(15)
#outputs : 5768

这里当n值变得很大的时候 会涉及到时间太长的问题 下面是用空间换时间的方法

//cpp

class Solution {
public:
    int stairs(int n) {
        vector<int> v;
        v[1] = 1;
        v[2] = 2;
        v[3] = 3;
        for(int i = 4; i <= n; ++i){
            v[i] = v[i - 1] + v[i - 2] + v[i - 3];
        }
        return v[n];
    }
};

---

下面是《剑指offer》里的问题 把跳台阶的格数扩展到n

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这里有一个很精妙的解法:
因为除了最后一阶台阶之外 每次跳台阶都只有两种选择 即跳或不跳 所以扩展到n就是2^(n-1)

//cpp
class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2,number-1);
    }
};

也可写为

//cpp
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<--number;
    }
};

然后是可以用归纳法的思想来解
手写 1阶 2阶 3阶 4阶 5阶 发现分别为1 2 4 8 16 所以n阶为2^(n-1)（大雾）