Steps to Develop a DP Algorithm

Dynamic programming is a design process. The three blocks below are the same ones used in every topic in this chapter; the numbered steps after them turn that model into a full solution.

Write the answer for each state (e.g. dp(k), dp(i, c)) as a formula using strictly smaller or simpler states. Typical patterns:

Explanation: The recurrence is the mathematical heart of DP: it must be correct (proved by optimal substructure) and finite (arguments eventually hit bases).

Map each state to storage (array, vector of vectors, or hash map). Use a sentinel for “not computed yet.” On each call for state s:

1. If base case applies, return the base value (often without memo, or after storing it).
2. If memo[s] is filled, return memo[s].
3. Otherwise compute using the recurrence, write memo[s], return.

Explanation: Memoization turns exponential recomputation into one solve per state — the same recurrence as brute force, but with a cache.

List the smallest arguments where the answer is known without the recurrence: empty set, zero capacity, zero length, amount zero, n ≤ 1 for Fibonacci, dp(0) = 0 for rod cutting, dp(0, c) = 0 for knapsack with zero items, etc.

Explanation: Bases anchor recursion. If they are wrong or missing, memoized code returns garbage or infinite loops.

Top-down: implement the recurrence recursively with memo (what the chapter code does).

Bottom-up: fill states in an order where every right-hand side is already known (tabulation).

If you need the actual choices (which items, which cut), backtrack from the optimal state using the recurrence to see which branch achieved max/min.

Count states × work per state. Watch pseudo-polynomial costs when a parameter like W or A is large. Space can sometimes be reduced if only recent rows of a table are needed (iterative trick; recursive memo usually keeps the full table).

Template for recursive DP:

Proportional to the number of memoized states and transitions per state.