Dynamic Programming

Dynamic programming solves a problem by computing each of its smaller subproblems once and storing the answer. The topic opens on the two properties that make that pay, using a tree of the calls plain recursion makes for fib(5), then designs a solution to the no-neighbours stall problem by defining a state and a recurrence and checking them by hand. A gotcha shows how swapping the two choices in the recurrence silently inflates the answer. Two cards then set memoisation, which computes states on demand, beside tabulation, which fills a table in order, with both written in three languages and both run on a million stalls, where only the table survives. A concept card rolls the table into two variables, another costs any dynamic programme as states times work and explains pseudo-polynomial time, and an exercise counts the readings of a door code from scratch.