Dynamic Programming

Dynamic programming solves problems by breaking them down into simpler overlapping subproblems.

Properties

1. Optimal Substructure: An optimal solution to the overall problem can be constructed from optimal solutions of its subproblems.
2. Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times.

Memoization vs Tabulation

• Memoization (Top-down): Start solving the given problem by breaking it down. If a subproblem was computed, return it.
• Tabulation (Bottom-up): Start solving the lowest level subproblem and build up to the main problem.