Dynamic Programming
Definition Dynamic Programming is a very powerful programming paradigm that can be employed to find optimal solutions to problems that possess the following properties: overlapping subproblems and optimal substructure. Overlapping subproblems A problem can be decomposed into smaller subproblems than can be reused multiple time to construct the overall solution The solutions to subproblems are often memoized to avoid re-work and improve time complexity Solutions to subproblems are reused more than once by subsequent solutions Optimal substructure The optimal solution to a problem can be constructed from the optimal solution of overlapping subproblems....