# 剑指Offer题解 - Day17

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

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

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

示例 1：

输入：n = 2
输出：2

1
2

示例 2：

输入：n = 7
输出：21

1
2

提示：

0 <= n <= 100

# 动态规划

本题考查动态规划。既然是动态规划，那么就需要先写出动态规划的方程。根据题目描述，青蛙每次可以跳一次台阶或者两次台阶。由此可得出以下结论：

当跳第零层台阶时，只有一种跳法，因此f(0) = 1
当跳第一层台阶时，只有一种跳法，因此f(1) = 1
当跳第二层台阶时，只有两种跳法，因此f(2) = 2
当跳第n层台阶时，要么先跳到f(n - 1)，然后再跳一层台阶到n层；要么先跳到f(n - 2)，然后再跳两层台阶到n层。因此可得：f(n) = f(n - 1) + f(n - 2) 。

通过以上结论可以发现，其实本题就是类似求斐波那契数列的问题。

参考昨天的题解，我们可以得出以下代码：

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    let sum = 0; // 初始化和
    let a = 1; // 初始化第零层台阶的跳法
    let b = 1; // 初始化第一层台阶的跳法
    for (let i = 0; i < n; i++) {
        sum = (a + b) % 1000000007; // 大数取模
        a = b; // 两数交替前进
        b = sum;
    }
    return a;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度 O(n)。
空间复杂度 O(1)。

# 总结

本题是考查动态规划的问题。本题与斐波那契数列问题的唯一不同之处在于初始值不同，其中：

本题的初始值为：f(0) = 1, f(1) = 1, f(2) = 2
斐波那契的初始值为：f(0) = 0, f(1) = 1, f(2) = 1

求解此类问题，不可以使用暴力法进行求解，会产生很多无效的分支，时间复杂度是O(2^n) 。

而使用动态规划求解，可以将时间复杂度降至O(n) 。

剑指Offer题解 - Day16 剑指Offer题解 - Day18