斐波那契数列相关算法

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
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级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

//迭代的思想
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级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

//f(n)=f(n-1)+f(n-2)+...f(0),f(n-1)不管前面的走法，只差一步到n级，以此类推。
//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的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

/*
*考虑最后的情况，一个1*2 的矩形覆盖 f(n-1)，或者两个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;
        }
    }
}

这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？

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

/*
*递归的思想，递归到底的条件是n=1,2,3 的情况。n=4 时可以考虑 
drink的饮料数=先兑换的4/3+喝完空瓶兑换以及剩余空瓶兑换的（喝完的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);
    }
}