Dynamic Programming Fundamentals

Dynamic programming (DP) solves an optimisation (or counting) problem by combining answers to smaller overlapping subproblems. Where plain recursion recomputes the same subproblem many times, DP stores each answer once and reuses it. Where a greedy algorithm commits to one local choice, DP considers every feasible choice at a subproblem and keeps the best.

The GATE syllabus names DP as a design technique. This note states the two ingredients (optimal substructure and overlapping subproblems), shows the memoized and bottom-up styles on the classical rod-cutting problem, and records how to reconstruct a solution from a filled table. Concrete applications (LCS, knapsack, matrix-chain, Floyd-Warshall) live in later notes.

Divide and conquer also needs optimal (or exact) substructure, but its subproblems are independent: merge sort never sorts the same index range twice. Memoizing merge sort therefore gains nothing. DP is the right tool precisely when the same subproblem recurs.

Both compute the same values. Bottom-up makes the fill order explicit and avoids stack overflow; top-down computes only states that are actually needed.

Fill order. A bottom-up table must be filled so that every state is computed after all the states it reads. If $dp[i][j]$ reads $dp[i-1][\cdot]$ and $dp[i][j-1]$ (LCS, edit distance, knapsack), row-major order works. If it reads shorter intervals $dp[i][k]$ and $dp[k+1][j]$ (matrix-chain), fill by increasing interval length $j - i$; plain row-major order from the top row would read cells that are not yet filled.

A DP solution is completely described by:

Writing these four items before coding is the reliable habit.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$.

Input. A rod of integer length $n \ge 1$ and a price list $p[1..n]$, where $p[i]$ is the price of a piece of length $i$.

Output. The maximum revenue $r_n$ obtainable by cutting the rod into integer-length pieces (or leaving it uncut). Cuts are free.

Optimal substructure gives the recurrence

Here $i$ is the length of the first piece; the residual rod of length $n-i$ is solved optimally. The case $i = n$ is the uncut rod.

Time / space. Bottom-up: the outer loop runs $n$ times and the inner loop up to $j$ times, so $\Theta(n^2)$ time and $\Theta(n)$ space. Memoized: the same asymptotic bounds; each of the $n+1$ distinct lengths is solved once, and solving length $j$ costs $\Theta(j)$. Naive recursion without a table is $\Theta(2^n)$ (CLRS 3e, Section 15.1).

Reconstruction. Store with each $r[j]$ the first-piece length $s[j]$ that attained the maximum. Then emit pieces by walking $n,\, n-s[n],\, n-s[n]-s[n-s[n]],\, \ldots$ until length 0.

Edge cases. $n = 0$ returns revenue 0 and no pieces. The full rod length must be consumed, even with negative prices. For $n=2$, $p[1]=-1$, $p[2]=-100$, the best cut is $1+1$, with revenue $-2$, not the uncut piece. The memoized algorithm uses a reserved $-\infty$ sentinel, distinct from all finite revenues; the examples here use positive prices. Ties among several optimal first pieces are broken by the if q < ... test (the smallest $i$ wins); any tie-break is correct for the revenue.

Let $R$ be any optimal cutting of a rod of length $n$, and let the leftmost piece have length $i$. The remaining pieces form a cutting of length $n-i$. If that residual cutting were suboptimal, replacing it by an optimal one would raise the total revenue, contradicting optimality of $R$. Hence some optimal solution begins with a first piece of length $i$ followed by an optimal solution of length $n-i$. Maximising over every feasible $i$ yields $r_n$.

A naive recursive call for length $n$ spawns calls for every smaller length; those in turn spawn further calls. If $T(n)$ counts all calls, $T(0) = 1$ and $T(n) = 1 + \sum_{j=0}^{n-1} T(j)$, so $T(n) = 2^n$. The recursion tree has $2^{n-1}$ leaves for $n \ge 1$: each composition of $n$ as an ordered sum of positive integers is one root-to-leaf path. Distinct subproblems, however, are only the $n+1$ lengths $0,1,\ldots,n$. Memoization collapses the exponential tree onto a linear table.

Running time is measured against the input size in bits. A number $W$ occupies about $\lg W$ bits, so a bound like $\Theta(nW)$ (0/1 knapsack, coin change for amount $W$) is polynomial in the value $W$ but exponential in its length: doubling the number of bits of $W$ squares $W$. Such an algorithm is called pseudo-polynomial. It is fast when the numbers are small, and it does not contradict the NP-hardness of 0/1 knapsack. By contrast, rod cutting's $\Theta(n^2)$ bound is polynomial in the input size, since the input lists $n$ prices.

A density-greedy cut for rod cutting fails on the prices $p = [1, 20, 33, 36]$ for $n = 4$: density picks length 3 first (revenue $33 + p[1] = 34$), while two pieces of length 2 give $40$ (CLRS Exercise 15.1-2).

Prices (CLRS Figure 15.1 style): $p[1..4] = 1, 5, 8, 9$.

Bottom-up fill:

Revenue $r_4 = 10$, first piece $s[4] = 2$, residual length 2 with $s[2] = 2$: pieces $2+2$. The uncut rod is worth only 9.

The recurrence $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$ has optimal-substructure form (exactly two subproblems) and massive overlap. Bottom-up fills an array in $\Theta(n)$ time; with the golden ratio $\phi=(1+\sqrt{5})/2$, the naive tree has $\Theta(\phi^n)$ nodes. This is a counting / evaluation DP rather than an optimisation DP, but the same two ingredients apply (CLRS Exercise 15.1-5).

Count the ways to pay 5 with coins of value 1, 2 and 5 (unlimited supply).

Loop order versus meaning. The same one-line recurrence counts different things depending on which loop is outside. Coins outside gives combinations (4); amounts outside gives ordered sequences (9).

The minimum number of coins uses the same shape with $\min$: $c(0) = 0$, $c(a) = 1 + \min_{d \le a} c(a-d)$. For coins 1, 2 and 5 and amount 11 it gives 3 ($5+5+1$).

Plain recursive Fibonacci (fib(n) calls fib(n-1) and fib(n-2), with fib(0) and fib(1) as base cases) makes $2F_{n+1} - 1$ calls in total. For $n = 5$ that is 15 calls: fib(2) runs 3 times, fib(1) 5 times and fib(0) 3 times. With memoization each of fib(0) to fib(5) is computed once, in $\Theta(n)$ total time.

Common misconceptions.