題目描述
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

解析
解釋辦法多種
①因?yà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)
因?yàn)閒(n-1)=f(n-2)+f(n-3)+...+f(1)

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

②每個臺階都有跳與不跳兩種情況（除了最后一個臺階），最后一個臺階必須跳。所以共有2^(n-1)中情況

Java

/**
 *  遞歸，因?yàn)?的n次方可以按位運(yùn)算，所以效率很高
 * 運(yùn)行時間：17ms
 * 占用內(nèi)存：9104k
 */
public int jumpFloorII(int target) {
    if (target <= 2) {
        return target;
    }
    return 2 * jumpFloorII(target-1);
}

/**
 * 循環(huán)
 * 運(yùn)行時間：17ms
 * 占用內(nèi)存：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))