剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）

发布：2021年9月17日19:53:49

问题描述及示例

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：
输入：n = 2
输出：2

示例 2：
输入：n = 7
输出：21

示例 3：
输入：n = 0
输出：1

提示：
0 <= n <= 100

我的题解（动态规划）

这道题和之前做的爬楼梯和斐波那契数列是一样的，具体的思路可以参考下面博客：

参考：【算法-LeetCode】70. 爬楼梯（动态规划入门）_赖念安的博客-CSDN博客
参考：【算法-剑指 Offer】10- I. 斐波那契数列（递归；动态规划）_赖念安的博客-CSDN博客

有关动态规划的思路总结，也可以参看我之前写的博客：

参考：【算法-LeetCode】53. 最大子序和（动态规划初体验）_赖念安的博客-CSDN博客

另外，其实LeetCode官方也说了这题和爬楼梯那题一样：

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
  let dp = [];
  dp[0] = 1;
  dp[1] = 1;
  for(let i = 2; i <= n; i++) {
    dp[i] = (dp[i-1] + dp[i-2])% 1000000007;
  }
  return dp[n];
};


提交记录
执行结果：通过
51 / 51 个通过测试用例
执行用时：76 ms, 在所有 JavaScript 提交中击败了39.16%的用户
内存消耗：37.8 MB, 在所有 JavaScript 提交中击败了37.03%的用户
时间：2021/09/17 20:05

另外要提的两个点

• 初始化时，对 dp[0] = 1 的理解，这里我觉得可以这样想，dp[i] 可以看做是跳到第 i 级台阶有 dp[i] 种方案。这样想的话，dp[0] 那就是跳到第 0 级台阶只有 1 种方案，那就是戴着不动。
• 注意题目中要求最后结果要对特定值 1000000007 取余。这个取余操作不能简单地放到返回前，因为 n 值可能比较大，到你取余的时候可能早就已经溢出了（JavaScript对于整数的表示有一定范围，超过这个范围就溢出了），那个时候就已经晚了，所以应该在每次计算 dp[i] 时就加上取余操作。这样不会造成最后结果的错误吗？可以看看题友【@Krahets - 力扣（LeetCode）)】的解释：

就是因为没有注意这个取余操作，白白浪费了我两次提交……淦……

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年9月17日19:56:54

参考：面试题10- II. 青蛙跳台阶问题（动态规划，清晰图解） - 青蛙跳台阶问题 - 力扣（LeetCode）

注意，上面的是官方的【精选】题解

【更新结束】

有关参考

更新：2021年9月17日20:03:29
参考：【算法-LeetCode】70. 爬楼梯（动态规划入门）_赖念安的博客-CSDN博客
参考：【算法-剑指 Offer】10- I. 斐波那契数列（递归；动态规划）_赖念安的博客-CSDN博客
参考：【算法-LeetCode】53. 最大子序和（动态规划初体验）_赖念安的博客-CSDN博客