概述
题目链接：
LeetCode
问题描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
解题思路
n[0]=1,n[1]=1,n[2]=n[0]+n[1]=2…n[n]=(n[n-1]+n[n-2])%(1e9+7)
斐波拉契数列，当数据达到n>92后long long不够表示，所以题目中要求取模，由模的性质，可知取模后仍旧满足斐波拉契数列。以空间换时间，101个数组保存中间结果，用递归解题到n=41时会超时。
代码
非递归：
class Solution {
public:
int numWays(int n) {
long long mod = 1000000007;
if(n == 0 || n == 1) return 1;
long long out[101];
out[0] = 1, out[1] = 1;
int i;
for(i=2;i<=n;i++){
out[i] = (out[i-1] + out[i-2])% mod;
}
return out[n];
}
};
最后
以上就是傲娇大侠为你收集整理的Leecode 面试题10- II. 青蛙跳台阶问题（斐波拉契数列）的全部内容，希望文章能够帮你解决Leecode 面试题10- II. 青蛙跳台阶问题（斐波拉契数列）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复