剑指offer——斐波那契数列

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

解题思路：

把递归写成非递归

 1 public class Solution {
 2     public int Fibonacci(int n) {
 3         
 4         if (n==0)
 5             return 0;
 6         if(n==1)
 7             return 1;
 8         int first=0;
 9         int second =1;
10         int sum=0;
11         
12         for(int i=2;i<=n;i++)
13         {
14            sum=first+second;
15            first = second;
16            second = sum;
17         }
18         return sum;
19 
20     }
21 }

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

 1 public class Solution {
 2     public int JumpFloor(int target) {
 3         if (target==1)
 4             return 1;
 5         if (target==2)
 6             return 2;
 7         
 8         int first=1;
 9         int second =2;
10         int[] result = new int[target+1];
11         result[0]=0;
12         result[1]=1;
13         result[2]=2;
14         
15         int sum=0;
16         int a;
17         int b;
18         
19         for(int i=3;i<=target;i++)
20         {
21             a= result[i-2];
22             b= result[i-1];
23             result[i] = a+b;
24             a = b;
25             b=result[i];
26         }
27         return result[target];
28 
29     }
30 }

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

 1 public class Solution {
 2     public int JumpFloorII(int target) {
 3         
 4         int sum=2;
 5         if(target==1)
 6             return 1;
 7         if(target==2)
 8             return 2;
 9         for(int i=3;i<=target;i++)
10         {
11             sum=sum*2;
12         }
13         return sum;
14         
15     }
16 }

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

 1 public class Solution {
 2     public int RectCover(int target) {
 3         if(target==1)
 4             return 1;
 5         if(target==2)
 6             return 2;
 7         int sum=0;
 8         int first=1;
 9         int second=2;
10         for(int i=3;i<=target;i++)
11         {
12             sum=first+second;
13             first=second;
14             second=sum;
15         }
16         return sum;
17 
18     }
19 }