A methodology of programming that can systematically explore all possible solutions to a problem.
- breaks complex problems into easier overlapping sub-problems
When to use DP
- When you require an optimum value (max, min, etc)
- When you require the number of ways to do something (paths, etc)
- Future decisions depend on earlier decisions. In other words, a Greedy Algorithm cannot work