跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解析
因为青蛙只有跳1级和跳2级两种跳法；所以，n级台阶就相当于n-1级再跳一次1级的和n-2级再跳一次2级的。即f(n)=f(n-1)+f(n-2)。和斐波那契数列是一样的。

Java

/**
 * 递归
 * 运行时间：421ms
 * 占用内存：9180k
 */
public int jumpFloor(int target) {
    if (target <= 2) {
        return target;
    }
    return jumpFloor(target-1) + jumpFloor(target-2);
}

/**
 * 循环赋值
 * 运行时间：19ms
 * 占用内存：9208k
 * @param target
 * @return
 */
public int jumpFloor2(int target) {
    if (target <= 2) {
        return target;
    }
    int one = 1;
    int two = 2;
    int result = 0;
    for (int i = 3; i <= target; i++) {
        result = one + two;
        one = two;
        two = result;
    }
    return result;
}

Python

class JumpFloor:
    def jumpFloor(self, number):
        if number <= 2:
            return number
        return self.jumpFloor(number-1) + self.jumpFloor(number-2)

    def jumpFloor2(self, number):
        res = [0,1,2]
        while len(res) <= number:
            res.append(res[-1] + res[-2])
        return res[number]