What can be a newbie explanation for a dynamic programming?

Question

I am trying to learn the basics of Dynamic Programming (DP), and went through some the online resources i could get, such as...

1. What is dynamic programming?
2. Good examples, articles, books for understanding dynamic programming
3. Tutorial for Dynamic Programming
4. Dynamic Programming – From Novice to Advanced -- (I can't understand it properly (i.e. how to approach a problem using DP))

and till now i get to understand that

A dynamic problem is almost same that of recursion with just a difference (which gives it the power it is know for)

i.e. storing the value or solution we got and using it again to find next solution

For Example:

According to an explanation from codechef

Problem : Minimum Steps to One

Problem Statement: On a positive integer, you can perform any one of the following 3 steps.

1. Subtract 1 from it. ( n = n - 1 )
2. If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 )
3. If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 )

Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1

eg:

1. For n = 1 , output: 0
2. For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 )

3. For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

   int memo[n+1]; // we will initialize the elements to -1 ( -1 means, not solved it yet )

Top-Down Approach for the above problem

int getMinSteps ( int n ) {
    if ( n == 1 )  return 0;
    if( memo[n] != -1 ) return memo[n];
    int r = 1 + getMinSteps( n - 1 );
    if( n%2 == 0 )   r  =  min( r , 1 + getMinSteps( n / 2 ) );
    if( n%3 == 0 )   r  =  min( r , 1 + getMinSteps( n / 3 ) );
    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

Am i correct in understanding the dp, or can anyone explain it in a better and easy way, so that i can learn it and can approach a problem with Dynamic programming.

Answer 1

The Fibonacci sequence example from wikipedia gives a good example.

Dynamic programming is an optimization technique that transforms a potentially exponential recursive solution into a polynomial time solution assuming the problem satisfies the principle of optimality. Basically meaning you can build an optimal solution from optimal sub-problems. Another important characteristic of problems that are tractable with dynamic programming is that they are overlapping. If those problems are broken down into sub-problems that are repetitive, the same solution can be reused for solving those sub problems. A problem with optimal substructure property and overlapping subproblems, dynamic programming is a potentially efficient way to solve it.

In the example you can see that recursive version of the Fibonacci numbers would grow in a tree like structure, suggesting an exponential explosion.

function fib(n)
       if n <=1 return n
       return fib(n − 1) + fib(n − 2)

So for fib(5) you get:

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))

And so on in a tree like fashion.

Dynamic programming lets us build the solution incrementally using optimal sub-problems in polynomial time. This is usually done with some form of record keeping such as a table. Note that there are repeating instances of sub problems, i.e. calculating fib(2) one time is enough.

Also from Wikipedia, a dynamic programming solution

function fib(n)
   if n = 0
       return 0
   else
       var previousFib := 0, currentFib := 1
       repeat n − 1 times // loop is skipped if n = 1
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
   return currentFib

Here the solution is built up from previousFib and currentFib which are set initially. The newFib is calculated from the previous steps in this loop. previousFib and currentFib represent our record keeping for previous sub-problems.

The result is a polynomial time solution (O(n) in this case) for a problem whose recursive formulation would have been exponential (O(2^n) in this case).

Answer 2

There is wonderful answer How should I explain dynamic programming to a 4-year-old? Just quoting same here :

Writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper

"What's that equal to?"

counting "Eight!"

writes down another "1+" on the left

"What about that?" quickly "Nine!"

"How'd you know it was nine so fast?"

"You just added one more"

"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"