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 := 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
作者介绍
j
jaryue
V1