Dynamic Programming

Difference between Dynamic Programming and Divide and Conquer

The main difference between dynamic programming and divide and conquer is that in the case of the latter, sub problems are independent, whereas in DP there can be an overlap of sub problems.

GEEKSFORGEEKS

Dynamic Programming Strategy

By uing memoization [maintaining a table of sub problems already solved], dynamic programming reduces the exponential complexity to polynomial complexity (O( n2), O( n3), etc.) for many problems.

The major components of DP are:

• Recursion: Solves sub problems recursively. 
• Memoization: Stores already computed values in table (Memoization means caching). 

Dynamic Programming = Recursion + Memoization

Problems:

Books Problem

Problem1:  Convert the following recurrence to code.

See RecursiveSolution.cpp - Recursive hence time  complexity is more
DynamicSolution.cpp - Time Complexity O(n), Space Compexity O(n)

• 0/1 Kanpsack : See Program
  

 

•  Longest Common SubSequence - See Program