The Knapsack Family, and When the State Is a Set
Knapsack is one recurrence with a dozen disguises. Learn the family, then learn to put a set of items in the state with a bitmask when n is small.
Problem Solving From Zero11
Subject · 3 posts
dynamic programming
Dynamic Programming Is a Table You Fill In
Four questions turn a problem into a dynamic program: what is the state, what is the answer for a state, what is the base, and in what order do you fill it.
Problem Solving From Zero10
Memoisation: Paying Once for an Answer
The cheapest optimisation in programming: remember what you already worked out. One dictionary turns an exponential recursion into a linear one.
Problem Solving From Zero09