变态跳台阶

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

解析
解释办法多种
①因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+...+f(1)
因为f(n-1)=f(n-2)+f(n-3)+...+f(1)

所以f(n)=2*f(n-1)

②每个台阶都有跳与不跳两种情况（除了最后一个台阶），最后一个台阶必须跳。所以共有2^(n-1)中情况

Java

/**
 *  递归，因为2的n次方可以按位运算，所以效率很高
 * 运行时间：17ms
 * 占用内存：9104k
 */
public int jumpFloorII(int target) {
    if (target <= 2) {
        return target;
    }
    return 2 * jumpFloorII(target-1);
}

/**
 * 循环
 * 运行时间：17ms
 * 占用内存：9452k
 */
public int jumpFloorII2(int target) {
    if (target <= 2) {
        return target;
    }
    int one = 1;
    int two = 2;
    for (int i = 3; i <= target; i++) {
        one = two;
        two = 2 * two;
    }
    return two;
}

Python

class JumpFloorII:
    def jumpFloorII(self, number):
        result = 1
        for i in range(2, number+1):
            result = 2*result
        return result

    def jumpFloorII2(self, number):
        return 2**(number-1)


if __name__ == '__main__':
    jumpFloorII = JumpFloorII()
    print(jumpFloorII.jumpFloorII(6))
    print(jumpFloorII.jumpFloorII2(6))