Skip to main content

DP Fundamentals

TL;DR​

Dynamic programming solves problems by combining solutions to overlapping subproblems. Identify overlapping subproblems by analyzing recursive tree: if same state computed multiple times, DP applies. Verify optimal substructure: optimal solution contains optimal solutions to subproblems. Use memoization (top-down, recursive, caching) for intuitive but sparse problems. Use tabulation (bottom-up, iterative, table-building) for dense problems and better space optimization. Define clear states (variables defining subproblem), transitions (how to combine subproblem solutions), and base cases. Conversion from recursive solution with memoization to DP is straightforward: add cache lookup, store results.

Core Concepts​

Overlapping Subproblems​

Overlapping subproblems occur when recursive solution recomputes same subproblems multiple times.

Example: Fibonacci

F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)

Notice F(3) computed in both F(5) and F(4) recursion branches.

Identifying overlapping subproblems:

  1. Write naive recursive solution
  2. Draw recursion tree
  3. Look for repeated nodes (same parameters)
  4. If found, overlapping subproblems exist

Performance impact: Naive recursion O(2^n) becomes O(n) with memoization by computing each unique state once.

Optimal Substructure​

Optimal substructure means optimal solution contains optimal solutions to subproblems.

Formal definition: If optimal solution to problem P uses optimal solutions to subproblems P1, P2, ..., Pk, then P has optimal substructure.

Checking optimal substructure:

  1. Assume optimal solution exists for problem
  2. Show that optimal solution to problem contains optimal solutions to subproblems
  3. If contradiction exists, optimal substructure fails

Counter-example: Longest simple path in graph lacks optimal substructure (unlike shortest path).

Memoization (Top-Down)​

Memoization stores results of subproblems in cache during recursion.

Approach:

  1. Write recursive solution
  2. Add cache (dictionary/array) lookup
  3. Before computing, check cache
  4. After computing, store in cache

Characteristics:

  • Intuitive: Natural recursive structure
  • Sparse problems: Only computes needed states
  • Stack overhead: Recursion stack can cause stack overflow
  • Debugging: Easier to trace recursive calls

Recursion tree pruning: Cache prevents exploring same subtree multiple times.

Tabulation (Bottom-Up)​

Tabulation builds solution iteratively, filling table from simple to complex states.

Approach:

  1. Define table structure (array/matrix for DP states)
  2. Initialize base cases
  3. Iterate through states in dependency order
  4. For each state, compute from previously computed states

Characteristics:

  • Systematic: Clear iteration order
  • Dense problems: Computes all states efficiently
  • No recursion: Avoids stack overflow
  • Space optimization: Can optimize space by keeping only needed rows/columns

Dependency order: Process states such that all dependencies are computed first.

State Definition​

State represents a unique subproblem. Each state has unique parameters.

State variables:

  • Meaning: Each parameter represents one dimension of problem reduction
  • Independence: States should be independent or clearly dependent
  • Dimensionality: Number of variables determines DP table dimensions

Example: 0/1 Knapsack

  • State: dp[i][w] = maximum value using first i items with weight limit w
  • State variables: i (number of items considered), w (remaining capacity)
  • 2D table needed

State Transitions​

Transitions define how to compute state from previously computed states.

Transition equation:

dp[state] = combine(dp[dependency1], dp[dependency2], ...)

Common patterns:

  • Maximization: dp[i] = max(dp[j] + benefit)
  • Minimization: dp[i] = min(dp[j] + cost)
  • Counting: dp[i] = sum(dp[j]) for valid j
  • Boolean: dp[i] = any(dp[j] AND condition)

Base Cases​

Base cases are initial states with known solutions, where no further recursion needed.

Characteristics:

  • Simplest states: Smallest problem instances
  • Directly computable: No dependencies on other states
  • Necessary: Solution structure depends on reaching base cases
  • Sufficient: All other states reachable from base cases

Example: Fibonacci base cases

  • F(0) = 0
  • F(1) = 1

Key Concepts​

Recognizing DP Problems​

Check if problem has overlapping subproblems and optimal substructure. If yes, DP likely applies.

Memoization Implementation​

Add dictionary to recursive function, check before computing, store after computing.

Tabulation Implementation​

Build DP table iteratively, initializing base cases, then filling in dependency order.

Optimization Techniques​

Space optimization by keeping only necessary states from previous iterations.

Practical Example​

# Fibonacci with naive recursion
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Fibonacci with memoization (top-down)
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Fibonacci with tabulation (bottom-up)
def fib_tab(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]

# Fibonacci space-optimized
def fib_opt(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Test
print(fib_memo(10))  # 55
print(fib_tab(10))   # 55
print(fib_opt(10))   # 55

# Counting paths in grid
def count_paths_memo(m, n, memo=None):
    if memo is None:
        memo = {}
    if (m, n) in memo:
        return memo[(m, n)]
    if m == 1 or n == 1:
        return 1
    memo[(m, n)] = count_paths_memo(m - 1, n, memo) + count_paths_memo(m, n - 1, memo)
    return memo[(m, n)]

def count_paths_tab(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

print(count_paths_memo(3, 3))  # 6
print(count_paths_tab(3, 3))   # 6

Common Pitfalls​

warning

Not verifying optimal substructure: Assuming DP applies without checking can lead to incorrect solutions. Verify that optimal solution contains optimal subproblem solutions.

Wrong state definition: Unclear or incomplete state variables cause confusion and incorrect transitions. Clearly define what each state represents.

Inefficient transition: Not finding optimal way to combine subproblem solutions leads to wrong answers. Verify all valid transitions explored.

Base case errors: Incorrect or missing base cases break entire solution. Carefully handle smallest problem instances.

Off-by-one errors: Array indexing mistakes in tabulation cause crashes or wrong answers. Carefully manage DP table boundaries.

Not considering all dependencies: Missing dependencies means required states not computed yet. Verify dependency order correct.

Self-Check​

  1. How do you identify if a problem has overlapping subproblems? Can you give an example beyond Fibonacci?
  2. What is the relationship between memoization and tabulation? When would you choose one over the other?
  3. How do you verify a problem has optimal substructure?

One Takeaway​

info

Dynamic programming transforms exponential brute-force solutions into polynomial-time algorithms by exploiting overlapping subproblems and optimal substructure. The key insight is identifying that many recursive calls compute identical subproblems—caching results (memoization) or building table iteratively (tabulation) avoids recomputation. Clear state definition, proper transitions, and base cases transform intuitive recursive thinking into efficient algorithms. Master DP fundamentals and you unlock solutions to countless optimization problems.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • Bellman, R. (1954). "The Theory of Dynamic Programming." Bulletin of the American Mathematical Society, 60(6), 503-516.