斐波那契数列

递归

public int Fibonacci(int n) {
        if(n == 0 || n == 1)
            return n;
        return Fibonacci(n-1) + Fibonacci(n-2);
    } 

上面的纯递归的时间复杂度为2^n
下面对此算法进行了时间的优化，带备忘录的递归

public class Solution {
    // 0 1 1 2 3 5 8
    int[] dp = new int[45];
    public int Fibonacci(int n) {
        if(n == 0 || n == 1)
            return n;
        if(dp[n] != 0)
            return dp[n];
        return dp[n] = Fibonacci(n-1)+Fibonacci(n-2);
    } 
}