Dynamic Programming: Solving Each Subproblem Once

Dynamic programming solves a problem by breaking it into smaller subproblems, solving each one once, and storing its answer so that every later need for it is a lookup. This card covers the two properties a problem needs for that to pay off, using Fibonacci numbers as the first instance, and counts the work the storing saves.

Each Fibonacci number is the sum of the two before it: fib(0) = 0, fib(1) = 1, and fib(n) = fib(n − 1) + fib(n − 2). Written as plain recursion, that definition is one line of code, and it does far more work than it needs to. A run computed fib(5) that way and printed every call it made as a tree, with a note on each call whose answer had already been worked out elsewhere in the tree.

The tree has 15 calls to find fib(5), but only six different ones, fib(0) to fib(5). The whole right-hand subtree under fib(5) repeats the fib(3) worked out on the left, and fib(2) is worked out three times. The run counted each:

The waste grows fast: each extra n adds another copy of most of the tree, and the number of calls grows exponentially, about 1.6ⁿ. Storing each answer the first time it is computed cuts the work to one computation per distinct call, six for fib(5) and n + 1 for fib(n), so O(n).

Think of a long sum worked out on paper, with each intermediate total written in the margin the first time you reach it. The next time the same total is needed, you read it from the margin instead of adding it up again. The analogy breaks on how the note is found: you find a margin note by eye, while a program finds a stored answer by its exact key, such as the n in fib(n).

Two properties make this work. Overlapping subproblems: the recursion asks for the same smaller problem more than once, as fib(3) is asked for twice. Optimal substructure: the answer to the whole is built from the answers to the smaller problems, as fib(5) is built from fib(4) and fib(3), or, for a problem that asks for the best of something, the best answer is made of best answers to smaller problems.

Merge sort is the non-example. It splits a list into halves that never share an item, so no subproblem is asked for twice, and storing answers would save nothing. That is divide and conquer, where the subproblems are separate. Dynamic programming is for subproblems that overlap.

Reach for it when a recursive solution keeps asking the same question with the same arguments, which shows up as a call tree with repeated labels, or when a problem asks for the best, the fewest or the number of ways and each choice leaves a smaller problem of the same kind. The so-what is the cost: an exponential recursion becomes a polynomial one, often in a few changed lines.