The DP method & rod cutting

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:

1. Optimal substructure — an optimal solution to the whole problem contains optimal solutions to its subproblems.
2. 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)

1. Characterize the structure of an optimal solution (find the optimal substructure).
2. Recursively define the value of an optimal solution (write the recurrence).
3. Compute that value bottom-up, filling a table.
4. 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 = \max_{1 \le i \le n}\,(p_i + r_{n-i}), \qquad 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 = \Theta(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 $\Theta(n^2)$; bottom-up just has a smaller constant (no recursion stack).