What is Dynamic Programming?

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems.

Dynamic programming takes advantage of the fact that while solving a problem many of the sub-problems are encountered and solved multiple times.

If we store the solution of this sub-problem (Memo-ize) then no need of solving the sub-problem again, instead we refer to the memory location where the solution of the sub-problem is stored and get the solution.

Dynamic programming solves each sub-problem only once (the very first time), next time the same problem can be looked up in the memory.

A Naïve solution often ignores this fact and solves the sub-problem each time it is encountered.

Dynamic programming can be applied to problems exhibiting 2 properties:

1.  Overlapping Sub problemsA recursive algorithm solving the problem should solve the same subproblems over and over, rather than generating new subproblems.For example, consider recursive algorithm for generating Fibonacci Numbers.F_i+2 = F_i+1 + F_i
   F5 = F4 + F3 , F6 = F5 + F4Here F4 is solved in both F5 and F6.
2.  Optimal SubstructureSolution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems.

Dynamic Programming algorithms are used for optimization problem, (eg. Finding shortest path, minimum cost of multiplying matrices etc) where we need to maximize or minimize certain behaviour.

Dynamic programming is kind of exhaustive search, an intelligent brute force that examines all possible ways to solve the problem and pick the best solution.

Dynamic Programming can solve a problem in 2 ways:     

1.  Memoization/Top-Down Approach:A problem is divided into sub-problem, and solution of each sub-problem is searched in look up table. If solution already exist then it is returned else the sub-problem is computed and the result is stored in the lookup table.Initially lookup table is initialized with NULL.
2.  Tabulation/Bottom Up Approachsolve the sub-problems first and then combine the solution of these sub-problems stored in lookup table to solve the problem. Solution to bigger and bigger sub-problems is generated iteratively and ultimately solution to the original problem is obtained.