Dynamic Programming Tutorial and Implementation

Dynamic Programming or DP approach deals with a class of problems that contains lots of repetition. The main idea behind DP is that, if you have solved a problem for a particular input, then save the result and next time for the same input use the saved result instead of computing all over again.

In other words, if we already solved a subproblem, we need not solve it again and again instead use the value stored after solving the first time.

Ex: Calculating Fibonacci Numbers

    fib(4) = fib(3)+fib(2)= 3+2 = 5     
    fib(5) = fib(4)+fib(3) = 5+3 = 8     
    while computing fibonacci of 5, we used the value of fib(4)
    directly instead of recomputing it.

There are the following two ways to store  values of subproblems:

1. Top-Down Approach
2. Bottom-Up Approach

Top-Down Approach (Memoization)

Start solving the given problem by breaking it down and ensures that, a method doesn’t run more than once for the same given inputs by storing already computed results. Recursion uses the top-down approach.

                         fib(5)
                        /    \ 
                    fib(4)    fib(3)
                   /    \
             fib(3)      fib(2)
            /    \
      fib(2)      fib(1)
     /     \  
fib(1)=1   fib(0)=1

Top-down approach (Recursion)

Algorithm

fib(n,memo){
    if(n==1 || n==0)
        return n;
    if(memo[n] == 0)              //compute only first time
        memo[n] = fib(n-1)+fib(n-2);
    return memo[n];

 Bottom-Up Approach (Dynamic Programming)

Start solving from the trivial subproblem all the way up to the actual problem. In other words, start from the base state (ex fib(0) = 0) up to the actual destination state. The iterative method uses this approach.

step 1: fib(0) = 0
step 2: fib(1) = 1
step 3: fib(2) = fib(1)+fib(0) = 1+0 = 1
step 4: fib(3) = fib(2)+fib(1) = 1+1 = 2
step 5: fib(4) = fib(3)+fib(2) = 2+1 = 3

  Bottom-Up Approach (Iterative) 

Algorithm

fibonacci(n){
    fib[0] = 0;
    fib[1] = 1;
    for(i=2; i<=n; i++)                  //iterative approach
        fib[i] = fib[i-1]+fib[i-2];
    return fib[n];
}

Closing Note

1. To find out where to apply Dynamic Programming, first find out whether the solution requires us to compute the same subproblem again and again or does it contain overlapping subproblem? If yes, then it means we have to apply DP.
2. A DP approach must reduce the time complexity of a solution algorithm for a problem.
3. In the case of non-overlapping subproblems, DP and recursion work in the same way and in such cases we apply the divide-and-conquer approach.