03_Fibonacci数列

• 题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

• 解题思路

斐波那锲数列第0项F(0)=0;第一项F(1)=1;第二项F(2)=1;从F(2)开始后面每项等于前两项的和，通项公式F(n)=F(n-1)+F(n-2) n>=2;
为了尽量降低算法的时间和空间复杂度，采用动态规划的算法思想

java代码如下：

    public int Fibonacci(int n) {
        int f1=1;
        int f2=1;
        int fn=0;
        if(n==0)
            return 0;
        if(n==1||n==2)
            return 1;
     for(int i=3;i<=n;i++){
         fn=f1+f2;
         f1=f2;
         f2=fn;
     }
        return fn;
}

04_跳台阶

• 题目描述

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

• 解题思路

将n=0-5级的跳法数目列出来
n=0.......f(n)=0
n=1.......f(n)=1
n=2.......f(n)=2
n=3.......f(n)=3
n=4.......f(n)=5
n=5.......f(n)=8
发现F(n)=F(n-1)+F(n-2) n>=2;
正是斐波那锲数列问题的变形。因此解法相同。

Java代码如下：

    public int JumpFloor(int target) { 
    int f1=1;
    int f2=2;
    int fn=0;
   for(int i=3;i<=target;i++){
       fn=f1+f2;
       f1=f2;
       f2=fn;
   }
    if(target<3) 
        return target;
    return fn;
}

05_变态跳台阶

• 解题思路

与跳台阶类似，只是每一个数目的台阶多了一种跳法。
将n=0-5级的跳法数目列出来
n=0.......f(n)=0
n=1.......f(n)=1
n=2.......f(n)=2
n=3.......f(n)=4
n=4.......f(n)=8
n=5.......f(n)=16
总结出通项公式F(n)=2^(n-1)

java代码如下：

解法一：动态规划

 public int JumpFloorII(int n) {
        int f1 = 1, f2 = 2, fn = 0;
    for (int i = 3; i <= n; i++) {
        fn = 2 * f2;
        f1 = f2;
        f2 = fn;
    }
    if (n <= 2)
        return n;
    return fn;
}

解法二:使用pow()函数

 public int JumpFloorII(int n) {
    return (int)Math.pow(2,n-1);
    }

解法三：移位运算

 public int JumpFloorII(int n) {
     int a=1; 
     return a<<(n-1);
    }

05_矩阵覆盖

• 题目描述

我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

• 解题思路

和跳台阶如出一辙，解法相同

java代码如下：

    public int RectCover(int target) {
    int f1=1,f2=2,fn=0;
   for(int i=3;i<=target;i++){
       fn=f1+f2;
       f1=f2;
       f2=fn;
   }
    if(target<3)
        return target;
    return fn;
  }