loading...
Nlogn

DYNAMIC PROGRAMMING TUTORIAL AND IMPLEMENTATION

mayankjoshi profile image mayank joshi Updated on ・2 min read

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.

Posted on Mar 21 by:

mayankjoshi profile

mayank joshi

@mayankjoshi

I love system design and most of the time I find myself learning or designing one of them. I'm highly active on twitter, So ping me there.

Nlogn

nlogn is a Computer Science portal specially designed to help you prepare for product-based companies interviews by practicing a wide variety of problem-related to system Desing, Data-Structure and much more.

Discussion

markdown guide