Knowledge Vault

Dynamic Programming

2 min read

Dynamic Programming

Dynamic programming (DP) is an algorithmic technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the results to avoid redundant computation. It transforms exponential brute-force solutions into polynomial-time algorithms by trading space for time — a fundamental optimization strategy in computer science.

DP applies when a problem exhibits two properties: optimal substructure (an optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur many times). Classic examples include the Fibonacci sequence, shortest paths, knapsack problems, and sequence alignment.

Key Concepts

Top-Down (Memoization) — Start from the original problem, recurse into subproblems, and cache results. Natural to implement but carries call stack overhead.

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

Bottom-Up (Tabulation) — Build solutions iteratively from the smallest subproblems upward. Avoids recursion overhead and often enables space optimization.

def fib(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

State Definition — The hardest part of DP is defining what state to track. The state must capture enough information to make optimal decisions without including unnecessary dimensions that bloat the table.

Space Optimization — When only the previous row/state is needed (as in Fibonacci), reduce from O(n) space to O(1) by keeping only the necessary previous values.

Common Pitfalls

  • Failing to identify overlapping subproblems — if subproblems are independent, divide-and-conquer is more appropriate
  • Defining states with unnecessary dimensions, leading to excessive memory usage
  • Forgetting base cases in memoization, causing infinite recursion

Best Practices

  • Start with a recursive solution, verify correctness, then optimize with memoization
  • Draw the subproblem dependency graph to determine bottom-up iteration order
  • Look for opportunities to reduce space complexity by analyzing which prior states are actually referenced
  • greedy-algorithms — Alternative optimization approach that makes locally optimal choices without backtracking
  • big-o-notation — DP typically reduces time complexity from exponential to polynomial

Graph View

Backlinks