跳台阶问题

最近在刷一些数据结构的题，发现个很有趣的问题：跳台阶问题。

1. 第一题（引子）：输出菲波那切数列的第N项。

斐波那契数列含义（百度百科）：
指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）

菲波那切数列是一个很有趣的数列，并且在很多的科研领域都是有应用的（就不介绍有哪些应用了，因为太（wo）高（ye）深（bu）了（hui））。

那用程序怎么实现出来呢？首先根据定义：F(n)=F(n-1)+F(n-2) 作为程序员很容易想到可以使用递归来实现。没错，下面是递归的实现：

    public int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);   
    }

很好理解吧，递归的出口就是n=0，n=1，n=2的时候

但是这种做法有什么问题呢？简单来说这种做法的递归的深度是在是太深了。举个例子：
我们计算n为4的情况：那么我们需要做如下的计算：
Fibonacci(4) = Fibonacci(3) + Fibonacci(2);
= Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
看看，多做了多少计算。2 计算了 2次，1 计算了5次，0计算了3次。正常来说我们计算4次就可以了吧。这样相当于多做了4次。

那我们就像能不能用迭代的方式来，观察下数列，想了下，感觉靠谱：

public static int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        int i1 = 1;
        int i2 = 1;
        int count = 3;
        while (count++<=n) {
            int number = i1+i2;
            i1 = i2;
            i2 = number;
        }
        return i2;
    }

我们知道只需要把上次的计算的值用来作为这次计算了第一项值，来循环最后就求出了我们想要的第n项的值。

看到这你可能想问了：这和跳台阶有什么关系呢？不要着急来看下这个问题：

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

想一想看一看，发现是不是有种似曾相识的感觉，可以把这个问题分解成：
如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);那么假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)。那总的问题是不是就变成了F(n)=F(n-1)+F(n-2)。呵呵，这不就是菲波那切数列吗问题吗（虽然不是完全一样，前两项变成了 1 2了）。代码如下：

public static int Fibonacci(int n) {
        if(n == 0){
            return 0;
        }else if( n<=2 ){
            return 1;
        }
        int i1 = 1;
        int i2 = 1;
        //只把这里改成2就可以了，以为这个序列不是 1 1 2 3 5....了，是 1 2 3 5.... 少了个1
        int count = 2;
        while (count++<=n) {
            int number = i1+i2;
            i1 = i2;
            i2 = number;
        }
        return i2;
    }

看到这里你可能会恍然大悟，大叫原来如此。但你再看下下面这个问题：

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

如果你足够聪明，大概已经知道套路了，我们可以看下这个问题怎么分解成一个多项式：

f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)

分解完了然后怎么办呢？我们第一个想法可能是用递归啊，一个for循环，然后在for循环里递归求每个子项，然后等n为0的时候返回1就可以了。

我想说这么做也可以但是你感觉是不是很恶心，这运行起来栈的深度是不是要很深了。

那我们观察下，看能不能化简什么的。灵机一动，发下好像可以：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

完美，这回在用递归次数就明显下来了。
代码如下：
```
public int JumpFloorII(int target) {
        if (target <= 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
    }
```

做到这里，咱们是不是自然的想到，我们可以不可以算下：
####4. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法。

这回我想大家应该都会了这种套路了。我们先不说话，先列多项式：
f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
化简得：f(n) = 2f(n-1) - f(n-m-1)

OK，上代码：
```
    public static int JumpFloorIII(int target,int m ) {
        //当大于m的时候是上面的公式
        if(target > m){
            return 2*JumpFloorIII(target-1, m)-JumpFloorII(target-1-m, m);
        }
        //当小于等于m的时候就是和n级的相同了
        if (target <= 1) {
            return 1;
        } else {
            return 2 * JumpFloorIII(target - 1,target);
        }
    }
```

完美~~~