Dynamic Programming: Fibonacci Numbers and Change-Making

What Is Dynamic Programming?

Dynamic programming (DP) solves problems by:
1. Breaking them into overlapping sub-problems (same sub-problems computed repeatedly in naive recursion)
2. Storing (memoising) sub-problem solutions to avoid recomputation
3. Building up solutions bottom-up (iteratively) or top-down (memoised recursion)

Two key properties required:
1. Optimal substructure: Optimal solution contains optimal solutions to sub-problems
2. Overlapping subproblems: Same sub-problems recur many times

KEY TAKEAWAY: Dynamic programming converts exponential-time recursive solutions into polynomial-time solutions by storing results. The trade-off is using extra space.

Example 1: Fibonacci Numbers

Naive Recursion (Exponential)

FUNCTION Fibonacci(n)
    if n <= 1 then return n
    return Fibonacci(n-1) + Fibonacci(n-2)

Recurrence: $T(n) = T(n-1) + T(n-2) + O(1) = O(2^n)$ — catastrophically slow.

Why? Fibonacci(3) is computed multiple times throughout the recursion tree.

DP Solution (Linear — 1D array)

ALGORITHM FibonacciDP(n)
    if n <= 1 then return n

    dp ← array of size n + 1
    dp[0] ← 0
    dp[1] ← 1

    for i ← 2 to n do
        dp[i] ← dp[i-1] + dp[i-2]
    end for

    return dp[n]

Time complexity: $O(n)$
Space complexity: $O(n)$ (1D array)

Space-Optimised Version ($O(1)$ space)

ALGORITHM FibonacciOptimal(n)
    if n <= 1 then return n
    prev2 ← 0; prev1 ← 1
    for i ← 2 to n do
        curr ← prev1 + prev2
        prev2 ← prev1
        prev1 ← curr
    end for
    return prev1

Example 2: Change-Making Problem

Problem

Given coin denominations $[c_1, c_2, \ldots, c_k]$ and a target amount $S$, find the minimum number of coins needed to make exactly $S$.

DP Formulation

Let $dp[i]$ = minimum number of coins to make amount $i$.

Recurrence:
$$dp[i] = \min_{c \in \text{coins}} (dp[i - c] + 1) \quad \text{if } i - c \geq 0$$

Base case: $dp[0] = 0$ (0 coins needed for amount 0)

Algorithm (1D array)

ALGORITHM CoinChange(coins, S)
    dp ← array of size S + 1, all initialized to ∞
    dp[0] ← 0

    for i ← 1 to S do
        for each coin c in coins do
            if c <= i AND dp[i - c] + 1 < dp[i] then
                dp[i] ← dp[i - c] + 1
            end if
        end for
    end for

    if dp[S] = ∞ then return "No solution"
    return dp[S]

Worked Example

Coins: {1, 5, 10}, Target: 15

Result: 2 coins (10¢ + 5¢)

Time complexity: $O(S \times k)$ where $k$ = number of coin denominations
Space complexity: $O(S)$ (1D array)

DP vs. Greedy for Change-Making

Greedy (always take largest coin) works for standard denominations (1, 5, 10, 25 cents) but fails for others. Example: Coins {1, 3, 4}, Target = 6.
- Greedy: 4 + 1 + 1 = 3 coins
- DP: 3 + 3 = 2 coins (optimal)

EXAM TIP: Know how to fill in the DP table step by step. Show the array state after each iteration. Examiners award marks for correct table values, not just the final answer.