What is dynamic programming?
Dynamic programming algorithms solve problems by combining results of subproblems— just like divide and conquer algorithms.
“Those who cannot remember the past are condemned to repeat it.” – Dynamic Programming
Overlapping Subproblems: the subproblems of a given problem are not independent. In other words, two subproblems share a problem.
Optimal Substructure Property: the overall optimal solution of the problem can be constructed from the optimal solutions of its subproblems.
Dynamic programming patterns
There are two approaches which come in handy when a problem is to be solved using dynamic programming:
The memoized version of a problem is similar to the regular recursive version, except that it looks for the answer of a subproblem in a lookup table before computing its solution.