Dynamic Programming: The Four Steps

The Four-Step Methodology

Applying dynamic programming to a problem follows a standard pattern:

1. Characterise the structure of an optimal solution.
2. Recursively define the value of an optimal solution (the Bellman equation).
3. Compute the value, typically bottom-up (or top-down with memoisation).
4. Reconstruct the optimal solution from the computed table (if required, using backpointers).

Example: Virtual Machine Hosting Problem (Rod Cutting)

Given $n$ CPU cores and a price table $p[\ell]$ for a VM with $\ell$ cores, find the maximum revenue achievable by partitioning cores into VMs.

Step 1: Characterise the optimal structure

An optimal partition for $n$ cores cuts off a VM of some size $i$ (earning $p[i]$) and optimally partitions the remaining $n - i$ cores. The first cut must be optimal for its remainder.

Step 2: Recursive definition (Bellman equation)

Let $v(j)$ be the maximum revenue from $j$ cores:

$v(j) = \begin{cases} 0 & \text{if } j = 0 \\[4pt] \max\limits_{1 \le i \le j} \big(p[i] + v(j - i)\big) & \text{if } j > 0 \end{cases}$

Step 3: Compute bottom-up

m[0] = 0
for j = 1 to n:
    m[j] = max(p[i] + m[j-i] for i = 1 to j)
return m[n]

$\Theta(n^2)$ time, $\Theta(n)$ space. Each $m[j]$ is computed once using $O(j)$ lookups into already-computed smaller entries. The naive recursive version would be exponential.

Step 4: Reconstruct the solution

Store the choice of $i$ that achieved the maximum at each $j$: choice[j] = i. To reconstruct, start at $j = n$, output choice[j], subtract it, and repeat until zero.

Example: Weight-Independent Interval Scheduling

Given $n$ intervals $[s_i, f_i)$, maximise the number of non-overlapping intervals selected.

Step 1: Characterise

Sort intervals by finish time. An optimal schedule either includes the last interval $n$ (in which case it cannot include any interval overlapping with $n$) or excludes $n$.

Step 2: Recursive definition

Let $p(i)$ be the largest index $j < i$ such that interval $j$ does not overlap with interval $i$ (i.e. $f_j \le s_i$). Define:

$\text{OPT}(i) = \begin{cases} 0 & \text{if } i = 0 \\ \max\big(\text{OPT}(i-1),\; 1 + \text{OPT}(p(i))\big) & \text{if } i > 0 \end{cases}$

Step 3: Compute

$\Theta(n \log n)$ for sorting by finish time, then $\Theta(n)$ to fill the DP table after precomputing all $p(i)$.

Step 4: Reconstruct

Trace back: if $\text{OPT}(i) = \text{OPT}(i-1)$, skip interval $i$. Otherwise include $i$ and jump to $p(i)$.

Extracting the Programme

When computing the maximum in Step 3, also record which action achieved it. After filling the table, start from the original problem state and follow the recorded optimal actions to reconstruct the solution. This is equivalent to storing backpointers in a graph of states.

If multiple actions yield the same optimal value, any may be chosen; the problem asks for an optimal solution, not the unique optimal solution.

Summary

Step	Task
1	Characterise optimal structure
2	Write Bellman equation (recursive definition)
3	Compute value bottom-up (or memoised top-down)
4	Reconstruct solution via backpointers
Key insight	Identify states that maximise subproblem overlap
Common pitfalls	Exponential without memoisation; wrong state formulation causes poor overlap