There’s still more to do with dynamic programming. The recurrence relation we used to describe the number of coins needed to make n cents of change had just one parameter (and so a one-dimensional table/array), but our recurrence relations/recursive functions can have more parameters.
Memoization/DP can still work. We may need a table with more dimensions. In fact, we can in general use a hash table where the key is a tuple of the parameter values.
Off we go to the Longest Common Subsequence, then!
- Here are the new DP in 2-D notes for today.
- For next class, please read section 6.5 in the textbook. (No reading quiz, however.)
- Keep going on the assignment due Friday!
- Also, here’s auto-memoizing code in Racket (actually using CPSC 311’s PLAI language variant, but other than the testing framework, most of it should transfer to plain Racket) and a built-in auto-memoizing decorator in Python.