10(2)-青蛙跳台阶

普通青蛙跳台阶

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

直接考虑n阶时的情况。第n阶台阶可以从第n-1台阶跳1级到达，也可以从n-2阶跳2级到达。可以得到公式 f(n) = f(n-1) + f(n-2) 这其实就是斐波那契数列的表达式。

 public int JumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        int first = 1;
        int second = 2;
        int third = 0;
        for (int i = 3; i <= target ; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

该题还有一个升级版本:

变态青蛙跳台阶

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

和跳台阶相比，这种确实很变态。依然是找规律。

首先看下基准情况，即n=1和n=2的情况:

f(1) = 1; //跳到1级台阶一种跳法 f(2) = 2; //跳到2级台阶可以直接跳2级或者跳两次1级台阶 所以共两次

跳3级台阶，我们可以这么考虑：

• 直接跳到3级
• 先跳到2级台阶上再直接跳到3级
• 先跳到1级台阶在直接跳到3级

可以得到递推公式如下:

f(3) = f(2)+f(1) + 1；

f(4) = f(3)+f(2)+f(1)+1; ....

最后我们解一下上面的递推公式可得下面等式:

f(n) = 2 * f(n-1) 最后发现得到的结果很简单。

  public int JumpFloorII(int target) {
        int first = 1;
        int third = 0;
        if(target == 1){
            return first;
        }
        for(int i = 2; i <= target; i++){
             third = first * 2;
             first = third;
        }
        return third;
    }