2.6 Dynamic programming

• The difference between dynamic programming and greedy algorithms is that with dynamic programming, the subproblems overlap. That means that by "memoizing" solutions to some subproblems, you can solve other subproblems more quickly.
• In Divide and Conquer, the sub-problems are independent of each other while in case of Dynamic Programming, the sub-problems are not independent of each other (Solution of one sub-problem may be required to solve another sub-problem).
• Divide and Conquer
  

  Divide and Conquer works by dividing the problem into sub-problems, conquer each sub-problem recursively and combine these solutions. solves a problem by combining the solutions to sub-problems

  1. Partition the problem into non-overlapping sub-problems
  2. Solve the sub-problems recursively
  3. Combine their solutions to solve the original problem
• Dynamic Programming
  

  Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as an array or a hash table) for future references. These sub-solutions may be used to obtain the original solution and the technique of storing the sub-problem solutions is known as memoization.

• You may think of DP = recursion + re-use

  A classic example to understand the difference would be to see both these approaches towards obtaining the nth fibonacci number. Check this material from MIT.

• The principle of optimality
  No matter what the first decision, the remaining decisions must be optimal with respect to the state that results from this first decision Dynamic programming may be used only when the principle of optimality holds. Useful when the sub-problems are overlapping

  Solve an optimization problem by caching sub-problem solutions rather than recomputing them

  1. Verify that the principle of optimality holds
     
     
  2. Set up the dynamic-programming recurrence equations
  3. Solve the dynamic-programming recurrence equations for the value of the optimal solution
  4. Perform a traceback step in which the solution itself is constructed

  Recursive Simple, intuitive code Unless care is taken to avoid recomputing previously computed values, the recursive program will have prohibitive complexity

  Iterative Not require additional space for the recursion stack To minimize run time overheads, and hence to reduce actual run time, dynamic programming recurrences are almost always solved iteratively (no recursion).