Chapter 5: Dynamic Programming

Dynamic programming, often abbreviated as DP, is a powerful problem-solving technique used to optimise decisions that unfold over multiple stages. Instead of solving the same subproblems repeatedly, DP stores their results and reuses them. This makes it an essential tool for problems where naive recursion would otherwise cause exponential work.

Recognizing Overlapping Subproblems

The first clue that a problem can be approached with dynamic programming is the presence of overlapping subproblems, which are smaller instances that recur during computation. When a recursive approach recomputes the same results multiple times, dynamic programming can make it efficient by caching or tabulating those results.

Understanding problem structure

Dynamic programming relies on two structural features: optimal substructure and overlapping subproblems. Optimal substructure means that the best solution to a larger problem depends on the best solutions to its smaller parts. Overlapping subproblems mean those parts are reused across branches of the computation tree.

A simple recursive example

The Fibonacci sequence illustrates overlapping subproblems clearly. The naive recursive version of fib(n) calls fib(n-1) and fib(n-2), both of which call smaller values repeatedly, causing exponential growth in calls.

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

Memoization and Tabulation

Dynamic programming improves on naive recursion by storing partial results. There are two main techniques: memoization (top-down) and tabulation (bottom-up). Both rest on the same idea, which is to reuse what you already know instead of recomputing it.

Top-down memoization

Memoization adds a cache that records the answer for each argument the first time it is computed. Subsequent calls reuse the cached value instead of redoing the computation.

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

Bottom-up tabulation

Tabulation reverses the process. It starts from the smallest subproblems and builds upward until reaching the desired result. This version avoids recursion and often runs even faster.

def fib_tab(n):
  if n <= 1:
    return n
  table = [0, 1]
  for i in range(2, n + 1):
    table.append(table[i - 1] + table[i - 2])
  return table[n]

Example: Fibonacci and Knapsack

Two classic examples show dynamic programming in action: the Fibonacci sequence and the 0/1 knapsack problem. Fibonacci demonstrates the principle of reuse. Knapsack shows how to optimise resource allocation.

Fibonacci revisited

Both memoization and tabulation produce the same results for Fibonacci numbers. However, the iterative tabulation version uses only O(n) time and space. This demonstrates how DP eliminates redundant work.

Solving the 0/1 knapsack problem

In the 0/1 knapsack problem, each item has a weight and a value. The goal is to fill a knapsack of limited capacity with items that maximise total value without exceeding the weight limit. A greedy strategy often fails, but dynamic programming guarantees an optimal result.

def knapsack(weights, values, capacity):
  n = len(weights)
  dp = [[0] * (capacity + 1) for _ in range(n + 1)]

  for i in range(1, n + 1):
    w = weights[i - 1]
    v = values[i - 1]
    for c in range(capacity + 1):
      if w <= c:
        dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - w] + v)
      else:
        dp[i][c] = dp[i - 1][c]
  return dp[n][capacity]

Optimizing Paths and Resource Usage

Dynamic programming extends naturally to graphs and networks where we want to minimise cost or maximise efficiency. Many pathfinding and scheduling problems use DP ideas beneath the surface, even when they appear very different on the surface.

Shortest paths in directed acyclic graphs

When a graph has no cycles, shortest paths can be computed efficiently by processing vertices in topological order. Each vertex’s distance depends only on those before it, so no revisiting is needed.

def shortest_dag(n, edges, source):
  # edges: list of (u, v, w)
  adj = [[] for _ in range(n)]
  for u, v, w in edges:
    adj[u].append((v, w))

  # simple topological sort
  indeg = [0] * n
  for u, v, _ in edges:
    indeg[v] += 1
  order = [i for i in range(n) if indeg[i] == 0]
  for u in order:
    for v, _ in adj[u]:
      indeg[v] -= 1
      if indeg[v] == 0:
        order.append(v)

  dist = [float("inf")] * n
  dist[source] = 0
  for u in order:
    for v, w in adj[u]:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
  return dist

Resource allocation and scheduling

DP is widely used to allocate limited resources across competing tasks. Examples include task scheduling, project planning, and optimal investment decisions. Each stage builds on prior results, balancing cost and benefit as it proceeds.

Dynamic Programming in Everyday Scenarios

Outside pure computer science, dynamic programming principles show up in many fields, from finance to robotics to daily planning. Any process that breaks a large decision into smaller linked choices can benefit from this structured approach.

Route planning and navigation

Modern navigation software uses DP principles to compute efficient paths while adapting to real-time conditions. Algorithms such as Dijkstra’s or A* effectively reuse partial path costs and update them dynamically as new data arrives.

Planning and optimisation in daily life

Even routine decisions can mirror DP logic. When budgeting time or money, we naturally make local decisions that contribute to a long-term goal, often revising plans based on what we have already done. Recognising this recursive structure is what makes dynamic programming such an intuitive yet profound idea.