Dynamic Programming (DP) is an algorithmic paradigm or, more specifically, technique or method to solve some subclass of optimization and сombinatoric problems. Ability to solve the particular problem using DP based on the optimal substructure property, i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems. These subproblems are usually overlapped between each other, i.e. future "decisions" depend on earlier decisions.
Generally, there are two ways to implement a DP algorithm:
- Bottom-up approach (also named tabulation).
- Top-down approach.