A Brief Introduction to Dynamic Programming

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply store the results of subproblems, so that we do not have to re-compute them when needed later.

example

// recursion
public int fib(int n) {
    if(n<=1) return n;
  	return fib(n-1)+fib(n-2);
}
// dynamic programming
public int fibDP(int n) {
    if (n>1) {
        int fib=0, p1=1,p2=0;
        for (int i=2;i<=n;i++) {
            fib = p1+p2;
            p2 = p1;
            p1 = fib;
        }
        return fib;
    } else if (n==1) {
        return 1;
    } else  {
        return 0;
    }
}

Two pattern of solving DP problem:

1. Tabulation: bottom up
2. Memoization: top down

Four steps to solve DP problems

1. Determine the meaning of each DP element. It also determines the dimensions, the element type, and the size of the DP cache.
2. Initialize DP cache. Initialization is based on a small number of known states, such as the first two Fibonacci numbers.
3. Transition. We deduce the values of unknown DP elements from known states. For bottom-up DP, the transition process is usually based on loops. The order of loops depends on the transition equation.
4. Return the result. It may require additional traversals on the DP cache.