Module 65 Extra

Dynamic programming

Stop working out the same small question twice, keep each answer, and build bigger answers on top of the ones you kept. Memoization with a dict and functools.cache, bottom-up tables that need no recursion, coin change, paths through a grid, the longest common subsequence and edit distance with the answer read back from the table, and the 0/1 knapsack, with big tests where the plain recursive way takes exponential time.

Steps

1. Memoization
2. Bottom-up tables
3. Coin change
4. Paths through a grid
5. Longest common subsequence and edit distance
6. Challenge: the 0/1 knapsack