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

int jumpFloorII(int number) {
    if (number <= 0) {
        return -1;
    } else if (number == 1) {
        return 1;
    } else {
        return 2 * jumpFloorII(number - 1);
    }
}

非常规

int jumpFloorII(int number) {
    return 1<<--number;
}

每个台阶都有跳与不跳两种情况(除了最后一个台阶),最后一个台阶必须
跳,所以共用2^(n-1)中情况,1左移number-1位 也就是2的(number-1)次方。这个主要是觉得方法二有点巧妙所以发给大家看一下。

阅读原文