题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

分析：

青蛙第一步可以选择跳上1级台阶，则还剩n - 1级台阶需要跳，即F(n - 1)

青蛙第一步也可以选择跳上2级台阶，则还剩n - 2级台阶需要跳，即F(n - 2)

则总的跳法F(n) = F(n - 1) + F(n - 2)

解法1：普通递归

public class Solution {    public static int JumpFloor(int target) {     if(target<1){         return 0;      }      else if(target==1){         return 1;     }      else if(target==2){            return 2;      }     return JumpFloor(target-1)+JumpFloor(target-2);    }}

 解法2：斐波那契数列

一只青蛙可以跳上1级台阶，也可以跳上2两级台阶

当n = 1时，有1种跳法

当n = 2时，有2种跳法

当n = 3时，有3种跳法

当n = 4时，有5种跳法

当n = 5时，有8种跳法

可以很明显的观察出来后一项等于前两项的和，所以就可以想到斐波那契数列进行求解

用两个变量进行迭代即可求出总的跳法

public class Solution {    public static int JumpFloor(int target) {    int f1 = 0;    int f2 = 1;      while (target-- > 0)    {        f2 = f1 + f2;        f1 = f2 - f1;    }    return f2;}}

解法3：动态规划

 

public class Solution {    public static int JumpFloor(int n) {    if(n==0){        return 0;    }        int []array=new int [n+1];//注意Java不能用*array    array[0]=1;    array[1]=1;    for(int i=2;i<=n;i++){     array[i]=array[i-1]+array[i-2];       }                return array[n];}}

 

 

 

关于斐波那契的求解方法，读者可以参考，包括了递归，动态规范，矩阵快速幂多种解法，这里就不再赘述了。