【剑指Offer】斐波那契数列之青蛙跳台阶

题目

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

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

分析

分析问题一：

将跳法总数记为f(n)，可以知道f(1)=1，f(2)=2。当n>2时，第一次跳1级的话，还有f(n-1)种跳法；第一次跳2级的话，还有f(n-2)种跳法，所以可以推得f(n)=f(n-1)+f(n-2)，即为斐波那契数列。所以，用斐波那契的解法来解即可。

分析问题二：

解法一：

当n=1时，f(1)=1。

当n大于1时，归纳总结可知：跳上n级台阶，第一次跳1级的话，有f(n-1)种方法；第一次跳2级的话，有f(n-2)种方法……第一次跳n-1级的话，有f(1)种方法；直接跳n级的话，有1种方法，所以可以得到如下公式：

f(n) = f(n-1)+f(n-2)+......f(1)+1 （n≥2）

f(n-1) = f(n-2)+f(n-3)+.....f(1)+1 （n>2）

由上面两式相减可得，f(n)-f(n-1)=f(n-1)，即f(n) = 2*f(n-1) (n>2)

最终结合f(1)和f(2)，可以推得：f(n)=2^(n-1)

解法二：除了最后一个台阶外，其余的木板都有存在和不存在两种可能性，所以n-1块木板有2^(n-1)种跳法。

代码

package com.Fibonacci; //青蛙跳台阶的2种方式 public class FrogJump { public static int FrogJump1(int n){ if(n < 0){ return 0; } if(n == 1){ return 1; } return FrogJump1(n-1) + FrogJump1(n-2); } public static int FrogJump2(int n){ if(n < 0){ return 0; } if(n == 0){ return 1; } if(n == 1){ return 1; } int prePre = 0; int pre = 1; int result = 1; for(int i = 2; i <= n; i++){ result = prePre + pre; prePre = pre; pre = result; } return result; } public static void main(String[] args){ System.out.println(FrogJump2(3)); System.out.println(FrogJump2(4)); } }

package com.Fibonacci; public class HardFrogJump { //递归 public static int HardFrogJump1(int n){ if(n <= 0){ return 0; } if(n == 1) { return 1; } return 2 * HardFrogJump1(n-1); } //迭代 public static int HardFrogJump2(int n){ if(n <= 0){ return 0; } if(n == 1){ return 1; } int pre = 1; int result = 2; for(int i = 2; i <= n; i++){ result = 2 * pre; pre = result; } return result; } public static void main(String[] args){ System.out.println(); } }