Introduction to Dynamic Programming
Greedy algorithms are fun, but sometimes you need more power than what they can give you. Like Greedy problems, Dynamic Programming (DP) problems have overlapping optimal substructure. Unfortunately, what is often the best local choice can end up not giving you the best global solution. Dynamic programming allows us to take advantage of the overlapping substructure property to speed up the search.