The DP method & rod cutting

The two ingredients of DP, the four-step method, and rod cutting as the canonical example — value + reconstruction.

Why dynamic programming

Dynamic programming (DP) solves an optimization problem by combining solutions to overlapping subproblems, storing each subproblem's answer in a table so it is computed only once. ("Programming" here means a tabular method, as in linear programming — it predates writing code.)

DP applies exactly when a problem has two ingredients:

Optimal substructure — an optimal solution to the whole problem contains optimal solutions to its subproblems.
Overlapping subproblems — a naive recursion solves the same subproblems again and again.

When both hold, DP turns an exponential recursion into a polynomial table fill. Merge sort has neither — its left/right halves never overlap — so memoizing it buys nothing.

The four-step method (memorize this)

Characterize the structure of an optimal solution (find the optimal substructure).
Recursively define the value of an optimal solution (write the recurrence).
Compute that value bottom-up, filling a table.
Reconstruct an optimal solution from stored choices (optional — only if you need which choices, not just the value).

Worked example: rod cutting

A rod of length $n$ can be cut into integer pieces; a piece of length $i$ sells for price $p_{i}$ . Maximize total revenue $r_{n}$ .

Step 1 — substructure. An optimal cut makes a first piece of length $i$ (revenue $p_{i}$ ) and then cuts the remaining length $n - i$ optimally. If the remainder were cut suboptimally we could swap in the better cut for more revenue — contradiction. So:

Step 2 — recurrence. $r_{n} = 1 \leq i \leq n max (p_{i} + r_{n - i}), r_{0} = 0.$

There are only $n$ distinct subproblems ( $r_{0}, \dots, r_{n - 1}$ ) but the naive recursion CUT-ROD calls itself $2^{n - 1}$ times — that overlap is what DP eliminates.

Step 3 — bottom-up table. Fill $r [0], r [1], \dots, r [n]$ in order of increasing length. Each $r [j]$ tries all $j$ first cuts, so the work is $\sum_{j = 1}^{n} j = Θ (n^{2})$ .

Step 4 — reconstruct. Keep a second array $s [j]$ = the first-cut length that achieved $r [j]$ . To list the cuts: print $s [n]$ , set $n \leftarrow n - s [n]$ , repeat until $0$ . The value table alone cannot tell you which cut won — you need the stored-choice array.

Top-down memoization (recurse, but check the table first) gets the same $Θ (n^{2})$ ; bottom-up just has a smaller constant (no recursion stack).

Naive CUT-ROD on n = 3: eight calls for only four distinct subproblems. Every highlighted node is a rod length the recursion re-solves from scratch — that repetition is the overlap DP removes, and it doubles with every extra unit of length.

One cell of the table, computed. r[4] tries every first cut i and reuses the already-known r[4 - i]; the winner is stored in r[4] and the winning i in s[4]. Doing this for j = 1..n is the whole bottom-up algorithm.

The two tables the bottom-up pass produces for the price list used in the exercise. r[j] is the best revenue for length j; s[j] is the first cut that achieved it. Reconstruction chains through s: print s[10] = 10, drop to 10 - 10 = 0, stop — one uncut rod.