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

2021年11月25日 阅读数:1
这篇文章主要向大家介绍剑指 Offer 10- II. 青蛙跳台阶问题,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目

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

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

示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
示例 3:

输入:n = 0
输出:1
提示:

0 <= n <= 100spa

个人答案

class Solution {
int a=1,b=1;
int res;
public int numWays(int n) {


if(n<0) return -1;
else if(n==0) return 1;
else if(n==1) return 1;
else for(int i=1;i<n;i++){
res = a+b;
a=b;
b=res%1000000007;

}

return res%1000000007;
}
}

  • 若是只有0级台阶,不跳也算一种跳法
  • 若是只有1级台阶,那显然只有一种跳法
  • 若是有2级台阶,那么就有2种跳法,一种是分2次跳。每次跳1级,另外一种就是一次跳2级
  • 若是台阶级数大于2,设为n的话,这时咱们把n级台阶时的跳法当作n的函数f(n),记为,第一次跳的时候有2种不一样的选择:一是第一次跳一级,此时跳法的数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1),二是第一次跳二级,此时跳法的数目等于后面剩下的n-2级台阶的跳法数目,即为f(n-2),所以n级台阶的不一样跳法的总数为f(n)=f(n-1)+f(n-2),不难看出就是斐波那契数列

上一篇: JS 图片放大镜
下一篇: 剑指offer记录贴