剑指 Offer 10- II. 青蛙跳台阶问题

难度：简单

problem

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例1：

输入：n = 2
输出：2

示例2：

输入：n = 7
输出：21

示例3：

输入：n = 0
输出：1

solution

递归

输入n为台阶个数，$f(n)$为方式种类个数。

$f(0) = 1$
$f(1) = 1$
$f(2) = 2$

如果第一次跳一个台阶则这种情况下的方式个数为$f(n-1)$，如果第一次跳两个台阶则这种情况下方式个数为$f(n-2)$。

故而：

$$f(n) = f(n-1) + f(n-2)$$

斐波那契数列：1，1，2，3，5，8，13…

前两个数之和构成第三个数。

DP

n级台阶，每次只能跳1级或者2级，就是1和2的排列组合，总和等于n。

求排列组合的个数。

code

递归

递归算法在leetcode直接timeout。

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    if (n <= 1) return 1;
    if (n === 2) return 2;
    return (numWays(n - 1) + numWays(n - 2)) % (1e9 + 7);
};

DP

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    let tmp = [1, 1];

    for (let i = 2; i <= n; i++) {
        i % 2 === 0 ? tmp[0] = (tmp[0] + tmp[1]) % (1e9 + 7) : tmp[1] = (tmp[1] + tmp[0]) % (1e9 + 7);
    }

    if (n % 2 === 0) return tmp[0] % (1e9 + 7);
    return tmp[1] % (1e9 + 7);
};

trap

这个题的中间结果也要模1e9+7，实在是个大坑。