Optimal Substructure: The Property Both Techniques Need

Most interesting computational problems are optimisation problems: among exponentially many candidates, find the best one. Choosing a subset of $n$ jobs means searching $2^n$ subsets. Aligning two strings of length $n$ means searching an astronomical number of alignments. Enumeration is not an option.

Dynamic programming and greedy algorithms are two ways of not enumerating. Both make the same underlying move: express the answer in terms of answers to smaller versions of the same problem, so an exponential search collapses into a polynomial number of reusable pieces.

Neither works on every problem. Both rest on a structural property that the problem either has or does not have, and the real skill is recognising that property rather than memorising recurrences. This lesson establishes the property. The rest of the path builds both techniques on top of it.

A problem has optimal substructure when an optimal solution to it contains, inside it, optimal solutions to its subproblems.

Shortest paths are the canonical example. Suppose the shortest route from A to Z happens to pass through M. Then the A-to-M portion must itself be a shortest A-to-M route. If it were not, you could cut it out, paste a shorter one in its place, and end up with a shorter A-to-Z route, contradicting the assumption that you started with the best one.

That cut-and-paste argument is the standard proof of optimal substructure, and it is worth performing rather than assuming. The property is what licenses a recurrence: once you know an optimal solution decomposes into optimal sub-solutions, you can define the answer in terms of smaller answers, and that recurrence is your algorithm.

The property is not automatic. Change shortest path to longest simple path, a path that visits no vertex twice, and it disappears.

Take four vertices in a square: edges A-B, B-C, C-D, D-A. The longest simple path from A to C through B is A, B, C. Its A-to-B piece is the single edge A-B, which is emphatically not the longest simple A-to-B path: that would be A, D, C, B. Try the cut-and-paste substitution and you get A, D, C, B, C, which visits C twice and is not a path at all.

The substitution fails because the subproblems are not independent. The A-to-B leg and the B-to-C leg compete for one shared resource, the pool of unvisited vertices. Shortest path has no such coupling. Longest simple path is NP-hard, and the missing property is a genuine signal of that difficulty.

Optimal substructure alone does not make dynamic programming worthwhile. Merge sort has it: sorting an array reduces to sorting each half and merging the results. But merge sort's subproblems are disjoint. The left half and the right half share nothing, so there is nothing to reuse and no table worth building. That is divide and conquer.

Dynamic programming needs a second property: overlapping subproblems, meaning the recursion reaches the same subproblem many times over.

The Fibonacci recurrence is the smallest illustration. Computing $F(5)$ calls $F(4)$ and $F(3)$; then $F(4)$ calls $F(3)$ all over again. The recursion tree has exponentially many nodes, yet the number of distinct subproblems is only $n$. Every additional node is pure recomputation, and once you see it that way the fix writes itself.

Drawn as a tree, this recursion has exponentially many nodes. Drawn honestly, as a graph where identical subproblems are the same node, it has $n$ nodes and a handful of edges. Notice that $F(3)$ has two parents and $F(2)$ has two parents: those shared nodes are the overlap.

Every dynamic program is a directed acyclic graph of subproblems. The nodes are the states, the edges are the dependencies, and the answer flows from the leaves upward. That reframing is the whole technique, and the two standard implementations are just two ways of walking this graph: memoisation explores it lazily from the top, tabulation fills it in topological order from the bottom.

Memoisation caches each subproblem's answer the first time it is computed. Here is edit distance, the minimum number of insertions, deletions and substitutions turning one string into another, following the recurrence Wagner and Fischer published in the Journal of the ACM in 1974:

from functools import lru_cache

def edit_distance(a, b):
    @lru_cache(maxsize=None)
    def d(i, j):
        if i == 0: return j
        if j == 0: return i
        sub = 0 if a[i - 1] == b[j - 1] else 1
        return min(d(i - 1, j) + 1,      # delete
                   d(i, j - 1) + 1,      # insert
                   d(i - 1, j - 1) + sub)  # substitute
    return d(len(a), len(b))

The decorator is the entire optimisation. Without it the function is exponential. With it there are only $|a| \times |b|$ distinct argument pairs and each costs constant work beyond its recursive calls, so the running time is $O(nm)$.

Tabulation allocates the table up front and fills it in an order that guarantees every dependency is ready before it is needed. For edit distance that means looping $i$ from 0 upward and $j$ from 0 upward, because cell $(i,j)$ depends only on cells above and to the left.

The two forms compute identical values, so choose on practical grounds:

• Tabulation has no recursion overhead, cannot blow the call stack, and touches memory in a predictable pattern that the cache prefetcher likes. It is usually faster.
• Memoisation only ever visits states the problem actually reaches. When the table is large but sparsely used, that is the difference between feasible and not, and it saves you from working out a valid fill order by hand.

A recursion depth limit is the practical tell: if the natural recursion is thousands deep, tabulate.

Greedy algorithms need a third property, and it asks for much more. The greedy-choice property holds when a globally optimal solution can be reached by making a locally optimal choice, without consulting the subproblems at all.

Stated in dynamic programming terms, that is unusually sharp. A DP recurrence takes a minimum or maximum over several options, and it evaluates all of them because it does not know in advance which wins. Greedy applies exactly when you can prove ahead of time which branch is always in the optimum. Then you never build a table: make the choice, recurse once, done.

This is why greedy algorithms are so much faster and so much rarer. Dynamic programming spends polynomial time to avoid needing to know. Greedy converts that cost into a proof obligation.

The asymmetry in the last column is the most useful thing on this page. Greedy demands strictly more than DP, so any problem greedy solves, DP also solves, usually more slowly. The reverse is false. When you are unsure, dynamic programming is the safe answer and greedy is a speedup you earn by proving something.

And testing on examples proves nothing. Making change greedily is optimal with US coin denominations, but with denominations of 1, 3 and 4, making 6 greedily yields 4 + 1 + 1, three coins, while the optimum is 3 + 3, two coins.