Dynamic Programming

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
通过分析上面的解法我们可以发现，这个计算过程可以总结为一个式子 $fib(n) = fib(n-1) + fib(n-2)$
而在我们的recursion解法中，从上往下计算，会使得许多东西被重复计算，如 $fib(3)$ 在计算 $fib(4)$ 和 $fib(5)$ 的时候都需要被计算。因此，如果将已经计算过的值储存起来，就可以不需要重复计算了
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];
    }

接着，我们对这个解法进行进一步的优化，我们注意到计算 $fib(n)$ 的时候只需要它的前两个值，所以每次只要储存前两个值就好了，不需要从1到n都存。可以作如下优化

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;
    }