大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n深夯，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)鄙陡。
n<=39

//遞歸的思想
public class Solution {
    public int Fibonacci(int n) {
        if(n<=0){
            return 0;
        } else if(n==1 || n==2){
            return 1;
        } else{
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
}

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)生逸。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法

//迭代的思想
public class Solution {
    public int JumpFloor(int target) {
        int  temp_1=1,temp_2=2;
        int result=3;
        if(target<=0){
            return 0;
        } else if(target==1){
          return 1;
        } else if(target==2){
            return 2;
        } else{
            for(int i=1;i<target-1;i++){
                result=temp_1+temp_2;//考慮target=3 的情況牢屋，先算result
                temp_1=temp_2;
                temp_2=result;     
            }
            return result; //n>=3的return值
        }
    }
}

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)槽袄。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法烙无。

//f(n)=f(n-1)+f(n-2)+...f(0),f(n-1)不管前面的走法，只差一步到n級(jí)遍尺，以此類推截酷。
//f(n-1)=f(n-2)+f(n-3)+...f(0),得到f(n)=2f(n-1）
public class Solution {
    public int JumpFloorII(int target) {
        if(target==0 || target==1){
            return 1;
        }else {
            int result=1,temp=1;
            for(int i=2;i<target+1;i++){
              //迭代的思想
                result=2*temp;
                temp=result;
            }
            return result;
        }
    }
}

我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)21的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形狮鸭，總共有多少種方法合搅？

/*
*考慮最后的情況，一個(gè)1*2 的矩形覆蓋 f(n-1)歧蕉，或者兩個(gè)2*1的矩形覆蓋 f(n-2);和為f(n-1)+f(n-2)
*/
public class Solution {
    public int RectCover(int target) {
        if(target==1){
            return 1;
        } else if(target==2){
            return 2;
        } else if(target<=0){
            return 0;
        }else{
            int temp1=1,temp2=2;
            int result=0;
            for(int i=3;i<=target;i++){
                result=temp1+temp2;
              //更新temp1 的值
                temp1=temp2;
              //更新temp2 的值
                temp2=result;
                
            }
            return result;
        }
    }
}

這樣一道智力題：“某商店規(guī)定：三個(gè)空汽水瓶可以換一瓶汽水灾部。小張手上有十個(gè)空汽水瓶，她最多可以換多少瓶汽水喝惯退？”答案是5瓶赌髓，方法如下：先用9個(gè)空瓶子換3瓶汽水，喝掉3瓶滿的，喝完以后4個(gè)空瓶子锁蠕，用3個(gè)再換一瓶夷野，喝掉這瓶滿的，這時(shí)候剩2個(gè)空瓶子荣倾。然后你讓老板先借給你一瓶汽水悯搔，喝掉這瓶滿的，喝完以后用3個(gè)空瓶子換一瓶滿的還給老板舌仍。如果小張手上有n個(gè)空汽水瓶妒貌，最多可以換多少瓶汽水喝？

輸入3,10,81
輸出1,5,40

/*
*遞歸的思想铸豁，遞歸到底的條件是n=1,2,3 的情況灌曙。n=4 時(shí)可以考慮 
drink的飲料數(shù)=先兌換的4/3+喝完空瓶?jī)稉Q以及剩余空瓶?jī)稉Q的（喝完的4/3+剩下的4%3）
*/
int softWater(int n){
    if (n<=1){
        return 0;
    }
    else if(n==2 || n==3){
        return 1;
    } else{
        return n/3+softWater(n/3+n%3);
    }
}