j

jaryue

V1

2023/04/06阅读:19主题:默认主题

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 := 35
 for i, t := 50; 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

分类:

后端

标签:

后端

作者介绍

j
jaryue
V1