首页 Algorithm

# 题目描述

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

# 问题分析

假设跳 n 阶有 f (n) 种跳法。

若第一次跳 1 阶，剩下 n-1 阶，有 f (n-1) 种跳法；

若第一次跳 2 阶，剩下 n-2 阶，有 f (n-2) 种跳法；

...

若第一次跳 n-1 阶，剩下 1 阶，有 f (1) 种跳法；

若第一次跳 n 阶，有 1 种跳法。

则有 f (n) = f (n-1) + f (n-2) + ... + f (1) + 1，

f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1，

f(n) = 2*f(n-1)，

所以有斐波那契数列

f(n)={1ifn=12∗f(n−1)ifn>1f(n) = \begin{cases} 1 &\text{if } n = 1 \\ 2*f(n-1) &\text{if } n > 1 \end{cases}

# 代码实现

public int JumpFloorII(int target) {
    if (target <= 0) {
        return 0;
    } else if (target == 1) {
        return 1;
    } else {
        return 2 * JumpFloorII(target - 1);
    }
}

# 扩展思路

青蛙没遇到一个台阶，可选择跳或者不跳，除了最后一个台阶必须跳，所以有2(n−1)2^{(n-1)} 种跳法。

代码实现：

public int JumpFloorII(int target) {
    return 1 << --target;
}