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

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

题目描述

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

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

示例 1：

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

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

输入：n = 0 输出：1 提示：

0 <= n <= 100

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

解题思路

法1

动态规划
因为青蛙可以跳两个,也可以跳一个,所以最后一跳可以跳两个到达,也可以跳一格到达,
所以它跳n个的种类
f(n)=最后跳一个f(n-1)+最后跳两个f(n-2)
跳一个的方法f(1)=1,跳两个的方法f(2)=2
储存前两个跳的数目,可以避免不必要的重复运算\

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

执行结果

法1

func numWays(n int) int {
 if n == 0 {//跳0步有一种
  return 1
 }
 if n < 4 { //特殊情况
  return n
 }
 a, r := 3, 5
 for i, t := 5, 0; i <= n; i++ { //动态规划计算储存值
  t = r
  r = (r + a) % 1000000007 //答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
  a = t
 }
 return r
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 90.75% 的用户 通过测试用例： 51 / 51