Identifying Dynamic Programming Problems
While it is easy to solve a DP problem once you identify how it recurses, it is difficult to determine whether a problem can be solved using DP. For instance, the traveling salesman problem, where you are given a graph and wish to cover all the vertices in the least possible time, is something that can't be solved using DP. Every DP problem must satisfy two prerequisites: it should have an optimal substructure and should have overlapping subproblems. We'll look into exactly what they mean and how to solve them in the subsequent section.
Optimal Substructures
Recall the best path example we discussed earlier. If you want to go from point A to point C through B, and you know that's the best path, there's no point in exploring others. Rephrasing this: If I want to go from A to D and I know the best path from A to C, then the best route from A to D will include the path from A to C. This is called the optimal substructure...