Dynamic Programming

When to Use DP The problem can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times The problem has an "optimal substructure" - an optimal solution can be formed from optimal solut...