Dynamic Programming

Overview

Dynamic programming solves optimization problems by breaking them into smaller overlapping subproblems and storing solutions to avoid redundant computation. The technique applies to problems exhibiting optimal substructure, where an optimal solution contains optimal solutions to subproblems.

Richard Bellman coined the term in the 1950s while working on optimization problems at RAND Corporation. The method addresses problems where naive recursive solutions result in exponential time complexity due to repeated calculation of identical subproblems.

Dynamic programming transforms exponential algorithms into polynomial ones by trading memory for speed. A recursive Fibonacci implementation makes O(2^n) calls, while dynamic programming reduces this to O(n) with O(n) space.

The approach differs from divide-and-conquer algorithms. Divide-and-conquer splits problems into independent subproblems, while dynamic programming handles overlapping subproblems that share dependencies. Merge sort uses divide-and-conquer because subarrays split independently; computing Fibonacci numbers requires dynamic programming because F(5) depends on both F(4) and F(3), and F(4) itself depends on F(3).

Two implementation strategies exist: top-down with memoization and bottom-up with tabulation. Top-down starts with the original problem and recursively breaks it down, caching results. Bottom-up builds solutions iteratively from smallest subproblems upward.

Key Principles

Dynamic programming requires two properties in the problem structure:

Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems. For shortest path problems, if the shortest path from A to C goes through B, then the path segments A to B and B to C must themselves be shortest paths. This property allows building optimal solutions from optimal subsolutions.

Overlapping Subproblems: The recursive solution recomputes the same subproblems multiple times. Computing F(6) requires F(5) and F(4); F(5) requires F(4) and F(3); both paths compute F(4) independently. This overlap creates opportunities for caching.

The absence of either property makes dynamic programming inappropriate. Problems with optimal substructure but independent subproblems benefit from divide-and-conquer instead. Problems lacking optimal substructure require different approaches like greedy algorithms or backtracking.

Memoization implements top-down dynamic programming. The algorithm stores function results in a cache indexed by input parameters. When called with previously seen inputs, the function returns the cached result instead of recomputing. The recursion structure remains natural while eliminating redundant work.

def fibonacci_memo(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)
  
  memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
end

fibonacci_memo(50)  # Completes instantly
# => 12586269025

Tabulation implements bottom-up dynamic programming. The algorithm creates a table (typically an array or matrix) to store solutions to all subproblems, filling it iteratively from smallest to largest. This approach avoids recursion overhead and makes space optimization clearer.

def fibonacci_table(n)
  return n if n <= 1
  
  table = Array.new(n + 1)
  table[0] = 0
  table[1] = 1
  
  (2..n).each do |i|
    table[i] = table[i - 1] + table[i - 2]
  end
  
  table[n]
end

State definition determines the structure of dynamic programming solutions. The state captures all information needed to solve subproblems and make transitions. Poor state definitions lead to incorrect solutions or missed optimizations. For knapsack problems, the state includes both current item index and remaining capacity; tracking only one dimension loses critical information.

Transition equations define how to compute states from previously computed states. These recurrence relations form the mathematical core of dynamic programming solutions. For longest increasing subsequence, the transition compares extending existing sequences versus starting new ones.

Ruby Implementation

Ruby's built-in data structures make implementing dynamic programming solutions concise. Hash objects provide memoization caches with flexible key types. Array objects store tabulation tables with fast indexed access.

Hash-based memoization handles multi-dimensional state spaces naturally:

def min_path_sum(grid, row = 0, col = 0, memo = {})
  return grid[row][col] if row == grid.length - 1 && col == grid[0].length - 1
  return Float::INFINITY if row >= grid.length || col >= grid[0].length
  
  key = [row, col]
  return memo[key] if memo.key?(key)
  
  down = min_path_sum(grid, row + 1, col, memo)
  right = min_path_sum(grid, row, col + 1, memo)
  
  memo[key] = grid[row][col] + [down, right].min
end

grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
min_path_sum(grid)
# => 7

Ruby's Array class supports multi-dimensional tables through nested arrays. Initializing tables requires care to avoid reference sharing:

# Incorrect - all rows share the same array object
table = Array.new(3, Array.new(3, 0))
table[0][0] = 1  # Modifies all rows!

# Correct - each row is a separate array
table = Array.new(3) { Array.new(3, 0) }
table[0][0] = 1  # Modifies only first row

The Enumerator class chains operations for concise bottom-up solutions:

def coin_change(coins, amount)
  dp = Array.new(amount + 1, Float::INFINITY)
  dp[0] = 0
  
  (1..amount).each do |i|
    coins.each do |coin|
      dp[i] = [dp[i], dp[i - coin] + 1].min if coin <= i
    end
  end
  
  dp[amount] == Float::INFINITY ? -1 : dp[amount]
end

coin_change([1, 2, 5], 11)
# => 3  # (5 + 5 + 1)

Ruby's default_proc for hashes enables automatic memoization:

def climb_stairs(n)
  memo = Hash.new do |hash, key|
    hash[key] = key <= 2 ? key : hash[key - 1] + hash[key - 2]
  end
  memo[n]
end

climb_stairs(10)
# => 89

Block syntax clarifies state transitions in tabulation:

def longest_common_subsequence(text1, text2)
  m, n = text1.length, text2.length
  dp = Array.new(m + 1) { Array.new(n + 1, 0) }
  
  (1..m).each do |i|
    (1..n).each do |j|
      dp[i][j] = if text1[i - 1] == text2[j - 1]
        dp[i - 1][j - 1] + 1
      else
        [dp[i - 1][j], dp[i][j - 1]].max
      end
    end
  end
  
  dp[m][n]
end

longest_common_subsequence("abcde", "ace")
# => 3

Method parameters in Ruby pass by reference, allowing mutable memo caches without explicit returns:

def word_break(s, word_dict, start = 0, memo = {})
  return true if start == s.length
  return memo[start] if memo.key?(start)
  
  word_dict.each do |word|
    next unless s[start...start + word.length] == word
    if word_break(s, word_dict, start + word.length, memo)
      memo[start] = true
      return true
    end
  end
  
  memo[start] = false
end

word_break("leetcode", ["leet", "code"])
# => true

Practical Examples

Knapsack Problem: Given items with weights and values, maximize value without exceeding capacity. The state tracks current item index and remaining capacity:

def knapsack(weights, values, capacity)
  n = weights.length
  dp = Array.new(n + 1) { Array.new(capacity + 1, 0) }
  
  (1..n).each do |i|
    (0..capacity).each do |w|
      if weights[i - 1] <= w
        take = values[i - 1] + dp[i - 1][w - weights[i - 1]]
        skip = dp[i - 1][w]
        dp[i][w] = [take, skip].max
      else
        dp[i][w] = dp[i - 1][w]
      end
    end
  end
  
  dp[n][capacity]
end

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
knapsack(weights, values, 8)
# => 10  # Items 2 and 4: values 4 + 6

Edit Distance: Find minimum operations (insert, delete, replace) to transform one string into another. The state represents prefixes of both strings:

def edit_distance(word1, word2)
  m, n = word1.length, word2.length
  dp = Array.new(m + 1) { Array.new(n + 1, 0) }
  
  # Base cases: converting from/to empty string
  (0..m).each { |i| dp[i][0] = i }
  (0..n).each { |j| dp[0][j] = j }
  
  (1..m).each do |i|
    (1..n).each do |j|
      if word1[i - 1] == word2[j - 1]
        dp[i][j] = dp[i - 1][j - 1]
      else
        insert = dp[i][j - 1]
        delete = dp[i - 1][j]
        replace = dp[i - 1][j - 1]
        dp[i][j] = 1 + [insert, delete, replace].min
      end
    end
  end
  
  dp[m][n]
end

edit_distance("horse", "ros")
# => 3  # horse -> rorse -> rose -> ros

Maximum Subarray Sum: Find contiguous subarray with largest sum. Kadane's algorithm tracks maximum sum ending at each position:

def max_subarray(nums)
  current_max = global_max = nums[0]
  
  nums[1..-1].each do |num|
    current_max = [num, current_max + num].max
    global_max = [global_max, current_max].max
  end
  
  global_max
end

max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])
# => 6  # Subarray [4, -1, 2, 1]

Longest Palindromic Substring: Find longest substring reading same forwards and backwards. The state tracks whether substring from i to j forms a palindrome:

def longest_palindrome(s)
  n = s.length
  return s if n < 2
  
  dp = Array.new(n) { Array.new(n, false) }
  start, max_len = 0, 1
  
  # Single characters are palindromes
  n.times { |i| dp[i][i] = true }
  
  # Check two-character substrings
  (0...n - 1).each do |i|
    if s[i] == s[i + 1]
      dp[i][i + 1] = true
      start, max_len = i, 2
    end
  end
  
  # Check longer substrings
  (3..n).each do |len|
    (0..n - len).each do |i|
      j = i + len - 1
      if s[i] == s[j] && dp[i + 1][j - 1]
        dp[i][j] = true
        start, max_len = i, len
      end
    end
  end
  
  s[start, max_len]
end

longest_palindrome("babad")
# => "bab"  # or "aba"

Partition Equal Subset Sum: Determine if array can be partitioned into two subsets with equal sum. Reduces to subset sum problem:

def can_partition(nums)
  total = nums.sum
  return false if total.odd?
  
  target = total / 2
  dp = Array.new(target + 1, false)
  dp[0] = true
  
  nums.each do |num|
    (target).downto(num).each do |j|
      dp[j] = true if dp[j - num]
    end
  end
  
  dp[target]
end

can_partition([1, 5, 11, 5])
# => true  # [1, 5, 5] and [11]

Common Patterns

One-Dimensional State Space: Problems where state depends on single parameter. Fibonacci, climbing stairs, and house robber problems use 1D arrays or simple variable tracking:

def rob(nums)
  return 0 if nums.empty?
  return nums[0] if nums.length == 1
  
  prev2, prev1 = nums[0], [nums[0], nums[1]].max
  
  nums[2..-1].each do |num|
    current = [prev1, prev2 + num].max
    prev2, prev1 = prev1, current
  end
  
  prev1
end

rob([2, 7, 9, 3, 1])
# => 12  # Rob houses 0, 2, 4

Two-Dimensional Grid Traversal: Problems involving paths through matrices. State represents position in grid with transitions limited by movement rules:

def unique_paths(m, n)
  dp = Array.new(m) { Array.new(n, 1) }
  
  (1...m).each do |i|
    (1...n).each do |j|
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    end
  end
  
  dp[m - 1][n - 1]
end

unique_paths(3, 7)
# => 28

String Matching: Problems comparing or transforming sequences. State typically tracks positions in both sequences with transitions based on character comparisons:

def is_subsequence(s, t)
  return true if s.empty?
  
  s_idx = 0
  t.each_char do |char|
    s_idx += 1 if s[s_idx] == char
    return true if s_idx == s.length
  end
  
  false
end

is_subsequence("abc", "ahbgdc")
# => true

Decision Problems: Problems choosing whether to include elements. State represents choices made with transitions exploring include/exclude options. Subset sum and partition problems follow this pattern.

State Compression: Reducing space complexity by observing that current state depends only on fixed number of previous states. Fibonacci needs only two previous values, not entire array:

def min_cost_climbing_stairs(cost)
  prev2, prev1 = 0, 0
  
  cost.each do |c|
    current = c + [prev1, prev2].min
    prev2, prev1 = prev1, current
  end
  
  [prev1, prev2].min
end

min_cost_climbing_stairs([10, 15, 20])
# => 15

Backtracking to Reconstruct Solution: Dynamic programming computes optimal values but may require additional work to reconstruct the solution path:

def coin_change_with_path(coins, amount)
  dp = Array.new(amount + 1, Float::INFINITY)
  parent = Array.new(amount + 1, -1)
  dp[0] = 0
  
  (1..amount).each do |i|
    coins.each do |coin|
      if coin <= i && dp[i - coin] + 1 < dp[i]
        dp[i] = dp[i - coin] + 1
        parent[i] = coin
      end
    end
  end
  
  # Reconstruct path
  path = []
  current = amount
  while current > 0
    path << parent[current]
    current -= parent[current]
  end
  
  { count: dp[amount], coins: path }
end

coin_change_with_path([1, 2, 5], 11)
# => { count: 3, coins: [1, 5, 5] }

Performance Considerations

Time complexity analysis starts with counting unique subproblems and work per subproblem. Fibonacci with memoization computes each F(i) once, doing O(1) work per subproblem, yielding O(n) total time. Two-dimensional problems like edit distance compute O(m × n) states with O(1) work each, resulting in O(m × n) time.

Space complexity depends on implementation strategy. Top-down memoization stores all computed subproblems in the cache, matching time complexity in space. Bottom-up tabulation creates tables for all subproblems but often allows optimization.

State compression reduces space when current computations depend only on recent states. Two-row techniques for grid problems maintain only current and previous rows instead of full matrix:

def min_path_sum_optimized(grid)
  return 0 if grid.empty?
  
  m, n = grid.length, grid[0].length
  prev = Array.new(n)
  curr = Array.new(n)
  
  prev[0] = grid[0][0]
  (1...n).each { |j| prev[j] = prev[j - 1] + grid[0][j] }
  
  (1...m).each do |i|
    curr[0] = prev[0] + grid[i][0]
    (1...n).each do |j|
      curr[j] = grid[i][j] + [prev[j], curr[j - 1]].min
    end
    prev, curr = curr, prev
  end
  
  prev[n - 1]
end

This optimization reduces O(m × n) space to O(n), maintaining O(m × n) time complexity.

Hash versus array trade-offs affect performance. Arrays provide O(1) access with minimal overhead but require contiguous integer indices. Hashes support arbitrary keys with slightly higher constant factors. For dense integer state spaces, arrays outperform hashes. For sparse or non-integer states, hashes provide better memory efficiency.

Memoization overhead includes hash lookups and recursive call stack. Tabulation avoids recursion but may compute unnecessary subproblems. For problems where only fraction of subproblems contribute to final answer, memoization computes fewer states. When all subproblems contribute, tabulation provides better cache locality and lower overhead.

Ruby's garbage collector impacts dynamic programming performance with large state spaces. Creating many small objects stresses memory allocation. Preallocating tables and reusing objects reduces allocation pressure:

# Less efficient - creates many intermediate arrays
def compute
  n.times.map { |i| calculation(i) }
end

# More efficient - preallocates result array
def compute_optimized
  result = Array.new(n)
  n.times { |i| result[i] = calculation(i) }
  result
end

Common Pitfalls

Incorrect Base Cases: Missing or wrong base cases cause infinite recursion or wrong answers. Fibonacci requires explicit handling of F(0) and F(1). Recursion without base cases never terminates:

# Wrong - missing base case for n == 1
def fib_wrong(n)
  return 0 if n == 0
  fib_wrong(n - 1) + fib_wrong(n - 2)  # Infinite recursion at n == 1
end

# Correct
def fib_correct(n)
  return n if n <= 1
  fib_correct(n - 1) + fib_correct(n - 2)
end

State Definition Errors: Insufficient state information leads to incorrect solutions. For problems requiring multiple parameters, tracking only one dimension loses critical information:

# Wrong - tracks only amount, loses coin information
def coin_change_wrong(coins, amount, memo = {})
  return memo[amount] if memo.key?(amount)
  # State doesn't capture which coins were used
end

# Correct - no additional state needed for this problem
# but ensure memo key captures all relevant parameters

Off-by-One Errors: Array indexing mistakes corrupt state transitions. Converting between 0-based and 1-based indexing requires care:

# Wrong - accesses out of bounds
def lcs_wrong(s1, s2, i, j, memo = {})
  return 0 if i == s1.length || j == s2.length
  if s1[i] == s2[j]  # Should be s1[i-1] if using 1-based
    1 + lcs_wrong(s1, s2, i + 1, j + 1, memo)
  end
end

Memoization Key Collisions: Using inadequate keys for multi-parameter problems causes cache collisions. String concatenation creates ambiguous keys:

# Wrong - "12" and "1,2" produce same key "12"
memo["#{i}#{j}"]

# Correct - array keys or delimited strings
memo[[i, j]]
memo["#{i},#{j}"]

Modifying Shared References: Ruby passes arrays and hashes by reference. Sharing default objects between table rows creates unintended aliasing:

# Wrong - all rows reference same array
dp = Array.new(m, Array.new(n, 0))
dp[0][0] = 1  # Modifies column 0 in ALL rows

# Correct - each row gets separate array
dp = Array.new(m) { Array.new(n, 0) }

Forgetting to Return Memoized Values: Computing and storing results without returning them wastes cache:

# Wrong - computes but doesn't use cached value
def compute(n, memo = {})
  return base_case if n == 0
  memo[n] = expensive_computation(n)
  expensive_computation(n)  # Recomputes instead of returning memo[n]
end

# Correct
def compute(n, memo = {})
  return base_case if n == 0
  memo[n] = expensive_computation(n)
end

Integer Overflow: Problems involving large numbers require careful handling. Ruby handles arbitrary precision integers automatically, but intermediate calculations might overflow in languages with fixed-width integers. Being aware of potential overflow helps when translating solutions:

# Ruby handles this automatically
def catalan(n)
  return 1 if n <= 1
  dp = Array.new(n + 1, 0)
  dp[0] = dp[1] = 1
  
  (2..n).each do |i|
    (0...i).each do |j|
      dp[i] += dp[j] * dp[i - 1 - j]  # Can become very large
    end
  end
  dp[n]
end

catalan(20)
# => 6564120420  # Ruby handles large integers

Unnecessary Recomputation: Failing to recognize computed values as final leads to redundant work. Once a subproblem is solved, its value should not change:

# Wrong - recomputes already solved subproblems
def fib_inefficient(n, memo = {})
  return n if n <= 1
  memo[n] = fib_inefficient(n - 1, memo) + fib_inefficient(n - 2, memo)
  fib_inefficient(n - 1, memo) + fib_inefficient(n - 2, memo)  # Duplicate work
end

Reference

Common Dynamic Programming Problems

Implementation Strategy Selection

State Space Patterns

Optimization Techniques

Complexity Analysis Guide