Definition
Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems in a recursive manner.
Dynamic programming works when a problem has the following properties:
- Optimal substructure: An optimal solution can be constructed from optimal solutions of its sub-problems.
- Overlapping sub-problems: Solutions of same sub-problems are reused several times.