What is dynamic programming

• The technique of storing repeated computations in memory
• Use more space to take less time

可以用dynamic programming 解決的問題具備的兩大性質

1. optimal substructure

例如，可以表達為f(n) = f(n-1) + f(n-2)
A useful way to think about optimal substructure is whether a problem can be easily solved recursively. Recursive solutions inherently solve a problem by breaking it down into smaller subproblems. If you can solve a problem recursively, it most likely has an optimal substructure.
能用recession方法解決的問題一般可以用這種方法解決。

2. overlapping subproblems

Dynamic programming relies on overlapping subproblems, because it uses memory to save the values that have already been computed to avoid computing them again. The more overlap there is, the more computational time is saved.
重復計算，比如fib(5) = fib(4) + fib(3), 在計算fib (5) & fib(4)都需要計算fib(3)

解決一道interview問題的方法-- FAST

• First solution
• Analyze the first solution
• Identify the Subproblems
• Turn the solution around

下面以經典的計算Fibonacci numbers為例說明這個方法的使用

• First solution
  寫出最直觀的解法，在這里是recursion

public int fib(int N) {
        if(N <= 1) {
            return N;
        }
        return fib(N-1) + fib(N-2);
    }

• Analyze the first solution
  通過分析上面的解法我們可以發(fā)現，這個計算過程可以總結為一個式子
  而在我們的recursion解法中，從上往下計算，會使得許多東西被重復計算，如在計算 和的時候都需要被計算。因此，如果將已經計算過的值儲存起來，就可以不需要重復計算了
• Identify the Subproblems
  按照前面的分析，把計算過的值儲存在cache中，就減少了一部分計算量

public int fib(int N) {
        if(N < 2) {
            return N;
        } 
        int[] cache = new int[N+1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return fib(N, cache);
    }
    public int fib(int n, int[] cache) {
        if(cache[n] >= 0) {
            return cache[n];
        }
        cache[n] = fib(n-1, cache) + fib(n-2, cache);
        return cache[n];
    }

• Turn the solution around
  上面的解法還是一個從上到下的計算過程，現在我們要把這個過程倒過來，變成從下到上

public int fib(int N) {
        if(N < 2) {
            return N;
        } 
        int[] cache = new int[N+1];
        cache[1] = 1;
        for(int i = 2; i <= N; i++) {
            cache[i] = cache[i-1]+cache[i-2];
        }
        return cache[N];
    }

接著，我們對這個解法進行進一步的優(yōu)化，我們注意到計算的時候只需要它的前兩個值，所以每次只要儲存前兩個值就好了，不需要從1到n都存。可以作如下優(yōu)化

public int fib(int N) {
        if(N < 2) {
            return N;
        } 
        int n1 = 0, n2 = 1;
        for(int i = 2; i <= N; i++) {
            int n = n1 + n2;
            n1 = n2;
            n2 = n;
        }
        return n2;
    }