首页 Algorithm

# 题目描述

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

# 方法一

首先就是最笨的方法。

  1. n 个台阶全部跳 1 级台阶，有 1 种跳法。

  2. n 个台阶有一个跳 2 级台阶，有Cn−11C_{n-1}^1 种跳法。

  3. n 个台阶有一个跳 3 级台阶，有Cn−22C_{n-2}^2 种跳法。

    ...

  4. n 个台阶有一个跳 n/2 级台阶，有Cn−(n/2−1)n/2−1C_{n-(n/2-1)}^{n/2-1} 种跳法。

最后相加即可。

public int JumpFloor(int target) {
    if (target <= 0) {
        return 0;
    }
    int i = 0;
    int n = 0;
    while (i <= target / 2) {
        if (i == 0) {
            n += 1;
        } else {
            n += factorial(target - i, i);
        }
        i++;
    }
    return n;
}
/**
* 计算阶乘
*/
public int factorial(int a, int b) {
    long aa = 1, bb = 1;
    for (int i = 0; i < b; i++) {
        aa *= (a - i);
        bb *= (b - i);
    }
    return (int) (aa / bb);
}
# 方法二
其次可以采用找规律的方法。
f (1) = 1, f (2) = 2, f (3) = 3, f (4) = 5， 可以总结出 f (n) = f (n-1) + f (n-2) 的规律，但是为什么会出现这样的规律呢？假设现在 6 个台阶，我们可以从第 5 跳一步到 6，这样的话有多少种方案跳到 5 就有多少种方案跳到 6，另外我们也可以从 4 跳两步跳到 6，跳到 4 有多少种方案的话，就有多少种方案跳到 6，其他的不能从 3 跳到 6 什么的啦，所以最后就是 f (6) = f (5) + f (4)；这样子也很好理解变态跳台阶的问题了。
public int JumpFloor(int target) {
    if (target <= 0) {
        return 0;
    }
    if (target == 1) {
        return 1;
    }
    if (target == 2) {
        return 2;
    }
    int first = 1;
    int second = 2;
    int third = 0;
    for (int i = 3; i <= target; i++) {
        third = first + second;
        first = second;
        second = third;
    }
    return third;
}
# 方法三
最后一种方法，可以使用递归来解决。
对于 n 阶台阶来说，若最后一步跳了一个台阶，则有 f (n - 1) 种跳法；若最后一步跳了两个台阶，则有 f (n-2) 种跳法。则有斐波拉起序列
f(n)={1ifn=12ifn=2f(n−1)+f(n−2)ifn>=3f(n) = \begin{cases} 1 &\text{if } n = 1 \\ 2 &\text{if } n = 2 \\ f(n-1) + f(n-2) &\text{if } n >=3 \end{cases}
public int JumpFloor(int target) {
    if (target <= 0) {
        return 0;
    }
    if (target == 1) {
        return 1;
    } else if (target == 2) {
        return 2;
    } else {
        return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}