动态规划DP

1、求斐波那契数

Fibonacci以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），简单的理解就是从n=2开始，每一项都等于前两项的和。
首先使用常规的方法求斐波那契数，也就是根据其定义，使用递归

public static int getFib2(int n){
    if(n==0){
    	return 0;
	}         
    if(n<=2){
    	return 1;
    }
	return getFib2(n-1)+getFib2(n-2);
}

递归方法往往耗时，消耗内存。而且上面的方法有很多重复计算。例如，我在计算Fib(5)时，需要计算Fib(4)+Fib(3)；由于n=4,n=3均不是递归的终止条件，所以他们都需要再递归下去。先看Fib(4)：

由于Fib(4)由于没有到达递归的终止条件，仍然需要递归计算：Fib(3)+Fib(2)，然后Fib(3)再递归一次才终于计算出Fib(4)；

同理，Fib(3)也是这样算的。

不知道你有没有发现，在求Fib(5)时，我们就计算了两次Fib(3)，这就发生了多余的计算。

下面的就用DP来优化下。具体的细节也就是，使用一个输入来存储已经计算过的结果，比如上面的Fib(3)，当我们后面再次需要这个结果时，直接查询这个数组即可，这可比再算一遍要划得来。

public class Solution {
    
	public static int []dp =new int[100];	//定义存储表
	
    public static int getFib(int n){
        if(n==0){
            return 0;
        }
        if(n<=2){
            return 1;
        }
        if(dp[n]!=0){			//查表
            return dp[n];		
        }
        //当查询表后，发现没有计算过时，再使用递归来算，并存到表中
        dp[n]=getFib(n-1)+getFib(n-2);
        return dp[n];
    }
    
}

最后，来看下DP的降维打击：

public static void main(String[] args) {
    int n = 42;
    long start = System.currentTimeMillis();
    System.out.println(getFib(n));
    long s1 = System.currentTimeMillis();
    System.out.println("DP:"+(s1-start)+"ms");

    System.out.println(getFib2(n));
    System.out.println("DiGui:"+(System.currentTimeMillis()-s1)+"ms");
}