剑指offer10-II.青蛙跳台阶问题
10-II-青蛙跳台阶问题
来源:力扣(LeetCode)
链接: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n
级的台阶总共有多少种跳法。
答案需要取模 1e9 7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:2
示例 2:
输入:n = 7
输出:21
示例 3:
输入:n = 0
输出:1
提示:
0 <= n <= 100
解法
该题其实就是斐波拉契数列,因为前后元素关系满足 F ( n ) = F ( n − 1 ) F ( n − 2 ) F(n) = F(n-1) F(n-2) F(n)=F(n−1) F(n−2), 因为每次可以跳一层,也可以跳两层,那么第n层的结果可以是第n-1
层(跳一层)和第n-2
层(跳两层)的结果之和。
- 递归:由于给出了计算公式 F ( n ) = F ( n − 1 ) F ( n − 2 ) F(n) = F(n-1) F(n-2) F(n)=F(n−1) F(n−2),可以使用递归的方式获得最终的结果
- 迭代:由于每个元素的计算结果只与最近的两个元素的结果相关,可以使用两个变量保存这两个相关的结果,并迭代进行更新,这样就避免了类似于递归方式很多重复的中间计算
- 动态规划:由于每次选择可以有两种状态,跳一层还是两层,并且状态转移方程已经给出 F ( n ) = F ( n − 1 ) F ( n − 2 ) F(n) = F(n-1) F(n-2) F(n)=F(n−1) F(n−2),因此可以考虑使用动态规划的方式
代码实现
递归方法:
- python实现
class Solution:
def numWays(self, n: int) -> int:
if n == 0:
return 1
if n < 3:
return n
f_1 = 1
f_2 = 2
for i in range(3, n 1):
ans = (f_2 f_1) % 1000000007
f_1 = f_2
f_2 = ans
return ans
- c 实现
class Solution {
public:
int numWays(int n) {
if(n==0)
{
return 1;
}
if(n < 3)
{
return n;
}
int ans = 0;
int f_1 = 1;
int f_2 = 2;
for(int i=3; i<=n; i )
{
ans = (f_1 f_2) % 1000000007;
f_1 = f_2;
f_2 = ans;
}
return ans;
}
};
**迭代方法:**要注意迭代的终止,n要遍历到
- python实现
class Solution:
def numWays(self, n: int) -> int:
if n == 0:
return 1
if n < 3:
return n
f_1 = 1
f_2 = 2
for i in range(3, n 1):
ans = (f_2 f_1) % 1000000007
f_1 = f_2
f_2 = ans
return ans
- c 实现
class Solution {
public:
int numWays(int n) {
if(n==0)
{
return 1;
}
if(n < 3)
{
return n;
}
int ans = 0;
int f_1 = 1;
int f_2 = 2;
for(int i=3; i<=n; i )
{
ans = (f_1 f_2) % 1000000007;
f_1 = f_2;
f_2 = ans;
}
return ans;
}
};
动态规划方法:
- python实现
class Solution:
def numWays(self, n: int) -> int:
if n == 0:
return 1
if n < 3:
return n
dp = [0] * (n 1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n 1):
dp[i] = (dp[i-1] dp[i-2]) % 1000000007
return dp[n]
- c 实现
class Solution {
public:
int numWays(int n) {
if(n == 0)
{
return 1;
}
if(n < 3)
{
return n;
}
vector<int> dp(n 1);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i=3; i<=n; i )
{
dp[i] = (dp[i-1] dp[i-2]) % 1000000007;
}
return dp[n];
}
};
复杂度分析
- 时间复杂度: 递归超时,迭代 O ( n ) O(n) O(n),动态规划 O ( n ) O(n) O(n)
- 空间复杂度:迭代 O ( 1 ) O(1) O(1) , 动态规划 O ( n ) O(n) O(n)
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggbebb
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13