1.青蛙跳台阶问题

1.1问题描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100

1.2问题分析

我们可以这么想，青蛙要跳到第n阶，那么只有两种情况，第一种是从第n-1个台阶跳到n,第二种是n-2跳到第n，那么我们只要知道跳到n-1,n-2用的步数，然后两个相加就行了,我们把n层台阶问题变成n-1层和n-2层的问题，还可以吧n-1层变成n-3,n-2层的问题，这不就是一个递归吗，换言之我们就找到了一个规律f(n)=f(n-1)+f(n-2)

1.3代码

C代码：

int numWays(int n){ int arr[n+1]; if(n<=1) return 1;   arr[0]=1;//设置n=0时等于1是为了满足规律并不是跳0阶有一种跳法   arr[1]=1; for(int i=2;i<n+1;i++) {       arr[i]=(arr[i-1]+arr[i-2])%1000000007;//注意相加再取余数 } return arr[n]; } 

Java代码：

class Solution { public int numWays(int n) { int arr[]=new int[n+1]; if(n<=1) return 1;       arr[0]=1;       arr[1]=1; for(int i=2;i<n+1;i++) {         arr[i]=(arr[i-1]+arr[i-2])%1000000007; } return arr[n]; } } 

2.青蛙疯狂跳台阶问题

2.1问题描述

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

2.2问题分析

有两种思路：
1.找规律：
number = 0 时，ret = 0
number = 1 时，ret = 1
number = 2 时，ret = 2
number = 3 时，ret = 4
number = 4 时，ret = 8
…
number = n 时，ret = 2^(n-1)
2.贪心算法：
从第n个台阶开始倒推：
1：可能是从第n-1个台阶跳到第n个台阶（跳了1阶）
2：可能是从第n-2个台阶跳到第n个台阶（跳了2阶）
…
n-1：可能是从第1个台阶跳到第n个台阶（跳了n-1阶）
推得 f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(1)
f(n-1) = f(n-2) + f(n-3) + f(n-4) + … +f(1)
故 f(n) = f(n-1) + f(n-1)
=2 * f(n-1)

2.3代码实现

C代码：

 int jumpFloorII(int number) { if(number==1) return 1; int sum=1; for(int i=1;i<number;i++) {             sum*=2; } return sum; } 

Java代码：

public class Solution { public int JumpFloorII(int number) { if(number==1) return 1; int sum=1; for(int i=1;i<number;i++) {             sum*=2; } return sum; } }