Loading [a11y]/accessibility-menu.js

剑指 Offer 10- II. 青蛙跳台阶问题【DP】

题目描述

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

示例 3:

输入:n = 0
输出:1

提示:

0 <= n <= 100

解题思路

仔细阅读后,我们会发现,当n>1是,青蛙是可以从n-1级和n-2级跳上来的。也就是说:

跳到第n级台阶的跳法数就是=跳到第n-1级台阶的跳法数+跳到第n-2级台阶的跳法数

那么我们再注意下,第0级、第1级的次数,我们就能解决这道题了。

根据题目实例可知,跳到第0级有1种方法,第1级台阶也为1种办法。

这和斐波那契(Fibonacci)数列是一样的结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int numWays(int n) {
int a=0,b=1,res=1;
for(int i=1;i<=n;i++){
res=(a+b)%1000000007;
a=b;
b=res;
}
return res;
}
}

复杂度分析

时间复杂度: O(n)

空间复杂度: O(1)

资源

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

剑指 Offer 10- II. 青蛙跳台阶问题【DP】

http://example.com/2021/03/30/10-Ⅱ 青蛙跳台阶问题/

Author

John Doe

Posted on

2021-03-30

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.