Dynamic Programming – Solving Problems Like Fibonacci Efficiently

In our last post, we explored recursion and how it can simplify complex problems by breaking them into smaller pieces. But what happens when those pieces overlap and we waste time solving the same sub-problem multiple times?

That’s where dynamic programming (DP) shines.

Dynamic programming adds memory to recursion. It helps you solve problems once, store the result, and reuse it—making inefficient recursive solutions incredibly fast.

Fibonacci: A Classic Case

Let’s revisit the Fibonacci sequence:

0, 1, 1, 2, 3, 5, 8, 13, ...

Each number is the sum of the two before it.

Naive Recursive Approach

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

This is elegant, but terribly inefficient:

  • It recalculates the same values over and over
  • Time complexity: O(2^n) – exponential!

Memoization – Top Down DP

We can fix this with memoization, which caches results.

memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
  • Time complexity: O(n)
  • Space complexity: O(n)

This is top-down DP: you solve the big problem, caching the smaller ones as you go.

Tabulation – Bottom Up DP

Another approach is to build the solution from the ground up.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
  • No recursion stack
  • Can be optimized further to O(1) space with two variables

When to Use Dynamic Programming

Look for these signs:

  • Overlapping subproblems – Are you repeating the same computation?
  • Optimal substructure – Can you build the big solution from smaller ones?
  • Too slow recursion – Exponential time functions that feel redundant

Common use cases:

  • Fibonacci
  • Coin change
  • Longest common subsequence
  • Knapsack problems

Dynamic Programming in the Real World

  • Game AI – Reuse solved board states for efficient decision-making
  • Route optimization – Use DP in combination with graphs (like in Dijkstra’s Algorithm)
  • Train Tracks Solver – Our recursive solver could be optimized by storing visited states to avoid exploring redundant paths

Challenge Time! 🧠

  • Rewrite the naive fib(n) to use both memoization and tabulation.
  • Try solving the coin change problem: given coins [1, 2, 5] and target 11, how many ways can you make change?
  • What other problems you’ve solved before could benefit from DP?

Next up in CQH103: Greedy Algorithms – making the best decision at each step to (hopefully) find the optimal path.