剑指Offer题解 - Day17

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

力扣题目链接[1]

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

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

「示例 1：」

输入：n = 2
输出：2

「示例 2：」

输入：n = 7
输出：21

「提示：」

• 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;
};

• 「时间复杂度 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) 。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/57hyl5/