The Dynamic Programming Approach

Dynamic programming solves a problem by breaking it into sub-problems, solving each once, and storing the answer for reuse.

That storing is the entire idea. Divide-and-conquer also breaks problems up, but its sub-problems are independent — the two halves of a merge sort share nothing. Dynamic programming is for when sub-problems overlap, so the same one is needed again and again.

The two conditions

Dynamic programming applies when a problem has:

1. Optimal substructure — the answer is built from answers to smaller versions of the same problem.
2. Overlapping sub-problems — those smaller versions repeat.

Condition 1 alone gives you divide-and-conquer. It is condition 2 that makes storing worthwhile.

Fibonacci: the syllabus example

Naive recursion, from Module 3:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Its call tree for fib(5):

                    fib(5)
              /              \
          fib(4)            fib(3)      <-- computed again
         /     \            /    \
     fib(3)   fib(2)    fib(2)  fib(1)
     /   \     /   \
 fib(2) fib(1) ...

fib(3) appears twice, fib(2) three times, fib(1) five times. The overlap is the waste, and it compounds:

Over 2.6 million calls for a number you could write down in a minute.

Two ways to fix it

Top-down (memoisation) — keep the recursion, remember answers:

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Bottom-up (tabulation) — build from the smallest case upward, no recursion at all:

def fib_dp(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Both compute each $F(k)$ once. The call count drops from 2,692,537 to 30.

Recursion versus dynamic programming

The syllabus asks for this comparison directly.

The crucial point: dynamic programming is not the opposite of recursion. Memoisation is recursion — with a memory. What changes is not the structure of the solution but whether work is repeated.

Bottom-up is often better still

fib_dp above keeps only two variables, not a table of n entries, and uses no stack at all. When a bottom-up formulation exists it is usually the most economical of the three.

Where else dynamic programming applies

• Shortest paths through a grid or network
• The knapsack problem — best value within a weight limit
• Longest common subsequence — the basis of file diff tools
• Change-making with fewest coins

Each has answers built from smaller answers that recur. Spotting that recurrence is the skill.