Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
1) Overlapping Subproblems
2) Optimal Substructure
1) Overlapping Subproblems
2) Optimal Substructure
a) Memoization (Top Down):
b) Tabulation (Bottom Up):
b) Tabulation (Bottom Up):
a) Memoization (Top Down): The memoized program for a problem is similar to the recursive version with a small modification that it looks into a lookup table before computing solutions. We initialize a lookup array with all initial values as NIL. Whenever we need solution to a subproblem, we first look into the lookup table. If the precomputed value is there then we return that value, otherwise we calculate the value and put the result in lookup table so that it can be reused later.
b) Tabulation (Bottom Up): The tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from table.
2) How would you choose between Memoization and Tabulation?
Read full article from Dynamic Programming | Set 1 (Overlapping Subproblems Property) | GeeksforGeeks
