7.递归和循环

动态规划（递归）解题步骤：

　　1.将原问题拆分成子问题。

　　2.确认状态。

　　3.确认边界状态（初始条件）。

　　4.状态转移方程。

题一：【斐波那契数列】

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

分析：斐波那契数列：{0 1 1 2 3 5 8 13 21 44……}

　　F(0)=0

　　F(1)=1

　　F(2)=F(1)+F(0)

　　F(3)=F(2)+F(1)

　　...

　　F(n)=F(n-1)+F(n-2)

1 public class Solution {
2     //递归 O(2^n)
3     public int Fibonacci(int n) {
4         if(n==0||n==1) return n;
5         return Fibonacci(n-1)+Fibonacci(n-2);
6     }
7 }

 1 public class Solution {
 2     //循环O(N)
 3     public int Fibonacci(int n) {
 4         if(n==0||n==1) return n;
 5         int first = 1;
 6         int second =0;
 7         for(int i=2;i<=n;i++){
 8             first = first + second;//F(n)=F(n-1)+F(n-2)
 9             second = first - second;//F(n-1)=F(n)-F(n-2)此处是下一次循环所使用
10         }
11         return first;
12     }
13 }

题二： 【跳台阶】

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

分析：n=1时，只有一种跳法；

　　　n=2时，有1+1和2两种跳法；

　　　n=3时，当上一次跳到第二个台阶时再跳只有一种--跳一个，当上一次跳到第一个台阶时只有一跳法--跳两个（如果跳一个那么和第一种情况重复复）；

　　　n=n时，当上一次跳到第n-1个台阶时再跳只有一种--跳一个，当上一次跳到第n-2个台阶时只有一跳法--跳两个；

　　　就是斐波那契数列！

　　　【代码同题一】

　　　

题三：【变态跳台阶】

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

分析：n=n时，当上次一跳到n-1时有1种方法，当上次跳到n-2时也有一种，……，当上次跳到n=1时也只有一种；

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

　　　F(n-1) = F(n-2)+F(n-3)+F(n-4)+...+F(1)

　　　=>F(n)-F(n-1)=F(n-1)　　=>F(n)=2*F(n-1)

 1 public class Solution {
 2     public int JumpFloorII(int target) {
 3         if(target==0||target==1) return target;
 4         int res=1;
 5         for(int i=2;i<=target;i++){
 6             res = res*2;
 7         }
 8         return res;
 9     }
10 }

题四：【矩形覆盖】

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

 　F(n)=F(n-1)+F(n-2)  =>斐波那契数列

　【代码同题一】