Dynamic Programming

"I thought dynamic programming was a good name. It was something not even a Congressman could object to."

— Richard Bellman, inventor of dynamic programming.

Prerequisites: Backtracking

Dynamic programming has a reputation for being intimidating, but applying it is usually more procedural than mystical. Once you know how to identify the right recurrence relation, the implementation tends to follow a small number of repeatable patterns.

At a high level, we apply DP in two steps:

Foundations

Problem-Solving Step

A recurrence relation is a function or formula defined in terms of itself on smaller inputs.

A classic example is Fibonacci:

F(0) = 1
F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1

In interview problems, we are usually not given the recurrence relation up front. Finding it is often the hardest part.

Implementation Step

Once we have a recurrence relation, we need to turn it into efficient code.

Memoization is usually the easiest way to start because recurrence relations are naturally recursive.

Recurrence Relations

The easiest way to find a recurrence relation is to reuse the decision tree mindset from backtracking. Backtracking explores that tree to find all full solutions. Dynamic programming shifts the focus:

In Backtracking, we care about partial solutions. In dynamic programming, we care about remaining subproblems.

Problem 40.1 Road Trip

We are driving down a road with n rest stops between us and our destination. For each rest stop, our navigation software tells us the detour time required to stop there.

We are given an array times of positive integers. If we do not want to go more than 2 rest stops without taking a break, what is the minimum total detour time?

• Example 1: times = [8, 1, 2, 3, 9, 6, 2, 4]
  • Output: 6
• Example 2: times = [8, 1, 2, 3, 9, 3, 2, 4]
  • Output: 5
• Example 3: times = [10, 10]
  • Output: 0

Figure 1. A compact version of the chapter's road-trip example. One optimal plan is to stop at indices 1, 3, and 6.

Collapse

Solution 40.1 Road Trip

It is tempting to always pick the smallest delay among the next three rest stops, but that greedy strategy is not correct.

We find the solution by systematically building a recurrence relation.

1. Decision Tree

Each node chooses the next rest stop where we will take a break. From a given stop, we have three choices: go to the next rest stop, skip one, or skip two.

Figure 2. Different partial solutions can lead to the same remaining suffix, which is exactly what memoization exploits.

2. Remaining Subproblem

For each partial solution, the remaining subproblem is the suffix of rest stops after the current location.

Figure 3. Dynamic programming ignores how we got here and focuses on the work that still remains.

3. Recurrence Relation

Recurrence Relation: `delay(i)`

State Meaning

`delay(i)` represents the minimum delay needed to reach the destination starting from rest stop `i`.

delay(i)

General Case

At rest stop `i`, we incur `times[i]` delay, then we can jump ahead `1`, `2`, or `3` steps. We pick the jump that minimizes the remaining delay.

delay(i) = times[i] + min(delay(i + 1), delay(i + 2), delay(i + 3) )

Base Cases

If we have reached or passed the destination (index `n` or greater), no further delay is incurred.

delay(i) = 0, for i ≥ n

Original Problem

We can start our journey by skipping up to 2 rest areas. So our first stop can be index `0`, `1`, or `2`.

min(delay(0), delay(1), delay(2))

For times = [8, 1, 2, 3, 9, 6, 2, 4], the values look like this:

Index i	0	1	2	3	4	5	6	7
times[i]	8	1	2	3	9	6	2	4
delay(i)	13	6	7	5	11	6	2	4

So the original problem becomes:

min(delay(0), delay(1), delay(2)) = min(13, 6, 7) = 6

Elements Of A Recurrence Relation

Part	Purpose	Road Trip Example
Signature	How subproblems are identified	delay(i)
Description	What the recurrence computes	Minimum delay to reach the destination from rest stop i
Base cases	Directly solvable subproblems	delay(n - 1), delay(n - 2), delay(n - 3)
General case	How smaller answers combine	times[i] + min(...)
Original problem	How to recover the final answer	min(delay(0), delay(1), delay(2))

Typical aggregation methods:

Problem Type	Aggregation
Maximization	max
Minimization	min
Counting	sum
Feasibility	logical or

For a recurrence relation to be correct, every valid subproblem must be covered by either a base case or the general case.

Direct Recursive Version

python

Copy

def delay(times):  # Inefficient -- do not use in interviews.
    n = len(times)

    def delay_rec(i):
        if i >= n:
            return 0
        return times[i] + min(delay_rec(i + 1), delay_rec(i + 2), delay_rec(i + 3))

    # Works even if n < 3 because delay_rec safely handles i >= n
    return min(delay_rec(0), delay_rec(1), delay_rec(2))

This is correct, but it is exponential because many suffixes get recomputed.

Memoized Version

python

Copy

def delay(times):
    n = len(times)
    memo = {}

    def delay_rec(i):
        if i >= n:
            return 0
        if i in memo:
            return memo[i]
        memo[i] = times[i] + min(
            delay_rec(i + 1), 
            delay_rec(i + 2), 
            delay_rec(i + 3)
        )
        return memo[i]

    # Works even if n < 3 because delay_rec safely handles i >= n
    return min(delay_rec(0), delay_rec(1), delay_rec(2))

Memoization turns the runtime from exponential to linear because each distinct suffix is only solved once.

Why Are The Base Cases At The End?

We defined:

delay(i): minimum delay to reach the destination starting from rest area i

We could also have defined:

delay(i): minimum delay to reach rest area i from the start

That alternative would reverse the direction of the recurrence:

• base cases would appear at the beginning,
• choices would point left instead of right,
• the original problem would move to the end.

These are often called forward and backward recurrences. Both are valid, but they shine in different situations:

Aspect	Forward DP	Backward DP
Definition	"What is the cost to finish the remaining journey from here?"	"What is the cost to have reached this point from the start?"
Original Problem	Evaluate from the start: min(delay(0), delay(1), delay(2))	Evaluate at the destination: min(delay(n-1), delay(n-2), delay(n-3))
Base Case	Reaching the destination: delay(i) = times[i] for i >= n-3	Starting point: delay(i) = times[i] for i <= 2
General Case	Combines with future steps: delay(i) = times[i] + min(delay(i+1), delay(i+2), delay(i+3))	Combines with previous steps: delay(i) = times[i] + min(delay(i-1), delay(i-2), delay(i-3))
Why	Easiest for Top-Down Memoization. Matches a natural recursive decision tree.	Most natural for Bottom-Up Tabulation (iterative DP). Builds up solutions from index 0 up to n.

Since we are focusing on Top-Down Memoization first, the forward version is easier to map to decision trees, so it is the one used throughout this chapter.

Caching "something" does not automatically make an algorithm dynamic programming. DP is specifically about caching overlapping subproblems.

Collapse

Recipe 1: Memoization

memo = {}

def f(subproblem_id):
    if subproblem is a base case:
        return result directly
    if subproblem_id in memo:
        return memo[subproblem_id]
    memo[subproblem_id] = recurrence_relation_formula
    return memo[subproblem_id]

return f(initial_subproblem)

from functools import lru_cache

@lru_cache(None)
def f(subproblem_id):
    ...

Memoization Analysis

Memoized DP is often analyzed with two numbers:

1. The number of subproblems.
2. The non-recursive work for each subproblem.

Multiply them to get the total work. For Road Trip:

• Subproblems: n
• Non-recursive work: O(1)
• Total time: O(n)
• Extra space: O(n)

DP Variations

2D Input

The same recipe applies to grids too. Consider Max-Sum Path:

Given a non-empty R x C grid of positive integers, find the path from the top-left corner to the bottom-right corner with the largest sum. You may only go down or right.

• Example: grid = [[1, 5, 1], [2, 3, 2], [20, 1, 1]]
  • Output: 25
• Example: grid = [[5]]
  • Output: 5

• LeetCode 64 — Minimum Path Sum
  This is basically the mirror version of your problem.
  Your problem: maximize sum going right/down
  LC 64: minimize sum going right/down

Figure 4. In grid DP, a cell like (1, 1) can be reached from multiple partial paths, so it becomes a shared subproblem.

For this problem, each subproblem is identified by a coordinate pair (r, c).

import math

def max_path(grid):
    R, C = len(grid), len(grid[0])
    memo = {}

    def max_path_rec(r, c):
        # 1. Out-of-bounds base case (return -inf so it's ignored by max)
        if r >= R or c >= C:
            return -math.inf
            
        # 2. Destination base case
        if r == R - 1 and c == C - 1:
            return grid[r][c]
            
        if (r, c) in memo:
            return memo[(r, c)]
            
        # 3. General case for all valid cells
        memo[(r, c)] = grid[r][c] + max(
            max_path_rec(r + 1, c),
            max_path_rec(r, c + 1)
        )
        return memo[(r, c)]

    return max_path_rec(0, 0)

Analysis:

• Subproblems: R * C
• Non-recursive work: O(1)
• Total time: O(R * C)
• Extra space: O(R * C)

Non-Constant Number Of Choices

Sometimes each subproblem has a variable number of children.

Consider Min-Subarray-Sum Split:

Given a non-empty array arr of positive integers and a number k with 1 < k < n, split arr into k non-empty subarrays so that the largest subarray sum is minimized.

• Example: arr = [10, 5, 8, 9, 11], k = 3
  • Output: 17
  • Explanation: We can split the array into [10, 5], [8, 9], and [11]. Their sums are 15, 17, and 11. The largest of these is 17. Any other split has a larger maximum sum (e.g. [10], [5, 8, 9], [11] has sums 10, 22, 11 -> largest is 22).
• Example: arr = [10, 10, 10, 10, 10], k = 2
  • Output: 30
  • Explanation: We can split the array into [10, 10] and [10, 10, 10]. Their sums are 20 and 30. The largest is 30.

To solve this, our state needs two parameters: the current index i and the remaining number of subarrays x. At each step, we decide where the first subarray ends, and then recursively ask the subproblem to split the remaining elements into x - 1 subarrays.

import math


def min_split(arr, k):
    n = len(arr)
    memo = {}

    def min_split_rec(i, x):
        if (i, x) in memo:
            return memo[(i, x)]

        if n - i == x:  # Put each element in its own subarray.
            memo[(i, x)] = max(arr[i:])
        elif x == 1:  # Put all remaining elements in one subarray.
            memo[(i, x)] = sum(arr[i:])
        else:
            current_sum = 0
            res = math.inf
            for p in range(i, n - x + 1):
                current_sum += arr[p]
                res = min(res, max(current_sum, min_split_rec(p + 1, x - 1)))
            memo[(i, x)] = res

        return memo[(i, x)]

    return min_split_rec(0, k)

The key line in the loop is:

res = min(res, max(current_sum, min_split_rec(p + 1, x - 1)))

Read it from the inside out:

• current_sum = the sum of the first subarray if we cut at p
• min_split_rec(p + 1, x - 1) = the best possible answer for the rest of the array
• max(...) = if we choose this split, the final answer is the larger of those two values, because we care about the largest subarray sum
• min(res, ...) = among all possible split points p, keep the split whose largest subarray sum is as small as possible

Analysis:

• Subproblems: n * k
• Non-recursive work: O(n)
• Total time: O(n^2 * k)
• Extra space: O(n * k)

Knapsack-Style DP

Another very common DP family is take / skip problems with a second parameter such as remaining capacity or remaining target.

Consider Subset Sum:

Given an array nums of positive integers and a target target, return whether some subset of nums sums exactly to target.

• Example: nums = [3, 2, 7, 1], target = 6
  • Output: True
  • Explanation: We can take 3 + 2 + 1 = 6.
• Example: nums = [4, 6, 10], target = 7
  • Output: False

• Related interview problems
  This pattern shows up in LeetCode 416. Partition Equal Subset Sum and many coin-change / target-sum variations.

The state needs two parameters:

• which index we are considering
• which target we still need to make

def subset_sum(nums, target):
    n = len(nums)
    memo = {}

    def can_make(i, t):
        if t == 0:
            return True
        if i == n:
            return False
        if (i, t) in memo:
            return memo[(i, t)]

        res = can_make(i + 1, t)
        if nums[i] <= t:
            res = res or can_make(i + 1, t - nums[i])

        memo[(i, t)] = res
        return res

    return can_make(0, target)

This is still dynamic programming: the same pair (i, t) can be reached through many different take / skip histories, so memoization prevents recomputation.

Analysis:

• Subproblems: n * target
• Non-recursive work: O(1)
• Total time: O(n * target)
• Extra space: O(n * target)

Sequence DP

Another major family is sequence DP. These problems usually compare prefixes or suffixes of one or two strings / arrays.

The most common state shape is:

• f(i) for one sequence
• f(i, j) for two sequences

A classic example is Longest Common Subsequence (LCS), which the chapter studies later in Problem 40.7.

The important pattern is that sequence DP often asks:

• what happens if the current characters match?
• if they do not match, which smaller prefix / suffix should we try next?

Other common sequence-DP interview problems include:

• Longest Common Subsequence
• Longest Increasing Subsequence
• Longest Palindromic Subsequence
• Edit Distance
• Decode Ways

Once you recognize that the state is "where am I in each sequence?", these problems become much easier to model.

Problem Set

def min_detour(times, k):
    n = len(times)
    memo = {}
    
    def delay(i):
        if i >= n:
            return 0
        if i > n - k - 1:
            return times[i]
        if i in memo:
            return memo[i]
            
        res = math.inf
        for p in range(1, k + 2):
            res = min(res, delay(i + p))
            
        memo[i] = times[i] + res
        return memo[i]
        
    return min(delay(p) for p in range(k + 1))

def max_rating(ratings):
    n = len(ratings)
    memo = {}
    
    def rating_sum(i):
        if i >= n:
            return 0
        if i in memo:
            return memo[i]
            
        memo[i] = max(
            ratings[i] + rating_sum(i + 2), 
            rating_sum(i + 1)
        )
        return memo[i]
        
    return rating_sum(0)

def max_rating_bottom_up(ratings):
    n = len(ratings)
    if n == 0:
        return 0
    if n == 1:
        return ratings[0]
        
    dp = [0] * n
    dp[0] = ratings[0]
    dp[1] = max(ratings[0], ratings[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i - 1], dp[i - 2] + ratings[i])
        
    return dp[n - 1]

def max_rating_optimized(ratings):
    prev2 = 0
    prev1 = 0
    
    for rating in ratings:
        current = max(prev1, prev2 + rating)
        prev2 = prev1
        prev1 = current
        
    return prev1

Problem 40.4 Count 0-Sum Paths LeetCode 62

Similar to LeetCode 62. Unique Paths

Given a non-empty binary grid, return the number of paths from the top-left corner to the bottom-right corner whose path sum is 0. You may move down, right, or diagonally down-right.

Example 1Output: 7

0

1

1

0

0

0

1

0

0

Empty space

Obstacle

Example 2Output: 0

1

The starting cell is an obstacle, so no paths exist.

Figure 5. Three of the seven valid zero-sum paths in the chapter's main example.

Collapse

def count_zero_sum_paths(grid):
    if not grid or not grid[0]:
        return 0
        
    R, C = len(grid), len(grid[0])
    memo = {}
    
    def num_paths(r, c):
        if r >= R or c >= C or grid[r][c] == 1:
            return 0
        if r == R - 1 and c == C - 1:
            return 1
        if (r, c) in memo:
            return memo[(r, c)]
            
        memo[(r, c)] = (
            num_paths(r + 1, c) +
            num_paths(r, c + 1) +
            num_paths(r + 1, c + 1)
        )
        return memo[(r, c)]
        
    return num_paths(0, 0)

def num_ways():
    memo = {}

    def num_ways_rec(i):
        if i > 21:
            return 1
        if 16 <= i <= 21:
            return 0
        if i in memo:
            return memo[i]
        memo[i] = 0
        for card in range(1, 11):
            memo[i] += num_ways_rec(i + card)
        return memo[i]

    return num_ways_rec(0)

num_steps(i) = 1 + min( num_steps(i - 1), num_steps(i / 2) if i % 2 == 0, num_steps(i / 3) if i % 3 == 0)

def min_steps_to_one(n):
    memo = {}
    
    def num_steps(i):
        if i == 1:
            return 0
        if i in memo:
            return memo[i]
            
        res = num_steps(i - 1)
        if i % 2 == 0:
            res = min(res, num_steps(i // 2))
        if i % 3 == 0:
            res = min(res, num_steps(i // 3))
            
        memo[i] = 1 + res
        return memo[i]
        
    return num_steps(n)

lis(i): length of LIS starting at nums[i]

base cases:
none explicitly (every element is at least a subsequence of length 1)

general case:
lis(i) = 1 + max(lis(j) for all j > i if nums[j] > nums[i])
(if no such j exists, max is 0)

original problem:
max(lis(i) for all 0 <= i < n)

def length_of_lis(nums):
    n = len(nums)
    memo = {}

    def lis(i):
        if i in memo:
            return memo[i]
        
        max_len = 1
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                max_len = max(max_len, 1 + lis(j))
                
        memo[i] = max_len
        return max_len

    return max(lis(i) for i in range(n))

lps(l, r): length of LPS in s[l:r+1]

base cases:
if l > r: return 0
if l == r: return 1

general case:
if s[l] == s[r]:
    lps(l, r) = 2 + lps(l + 1, r - 1)
else:
    lps(l, r) = max(lps(l + 1, r), lps(l, r - 1))

original problem:
lps(0, len(s) - 1)

def longest_palindrome_subseq(s):
    memo = {}
    
    def lps(l, r):
        if l > r:
            return 0
        if l == r:
            return 1
            
        if (l, r) in memo:
            return memo[(l, r)]
            
        if s[l] == s[r]:
            memo[(l, r)] = 2 + lps(l + 1, r - 1)
        else:
            memo[(l, r)] = max(lps(l + 1, r), lps(l, r - 1))
            
        return memo[(l, r)]

    return lps(0, len(s) - 1)

Solution Reconstruction

So far, most optimization problems only asked for the value of the solution. Sometimes we want the actual optimal solution itself. The chapter uses Longest Common Subsequence (LCS) as the main example.

lcs(i1, i2): length of the LCS of suffixes s1[i1:] and s2[i2:]

base cases:
lcs(n1, i2) = 0
lcs(i1, n2) = 0

general case:
if s1[i1] == s2[i2]:
    lcs(i1, i2) = 1 + lcs(i1 + 1, i2 + 1)
else:
    lcs(i1, i2) = max(lcs(i1 + 1, i2), lcs(i1, i2 + 1))

original problem:
lcs(0, 0)

def lcs(s1, s2):
    memo = {}

    def lcs_rec(i1, i2):
        if i1 == len(s1) or i2 == len(s2):
            return 0
        if (i1, i2) in memo:
            return memo[(i1, i2)]
        if s1[i1] == s2[i2]:
            memo[(i1, i2)] = 1 + lcs_rec(i1 + 1, i2 + 1)
        else:
            memo[(i1, i2)] = max(lcs_rec(i1 + 1, i2), lcs_rec(i1, i2 + 1))
        return memo[(i1, i2)]

    return lcs_rec(0, 0)

def lcs_reconstruction(s1, s2):
    memo = {}

    def lcs_rec(i1, i2):
        if i1 == len(s1) or i2 == len(s2):
            return ""
        if (i1, i2) in memo:
            return memo[(i1, i2)]
        if s1[i1] == s2[i2]:
            memo[(i1, i2)] = s1[i1] + lcs_rec(i1 + 1, i2 + 1)
        else:
            opt1 = lcs_rec(i1 + 1, i2)
            opt2 = lcs_rec(i1, i2 + 1)
            if len(opt1) >= len(opt2):
                memo[(i1, i2)] = opt1
            else:
                memo[(i1, i2)] = opt2
        return memo[(i1, i2)]

    return lcs_rec(0, 0)

def lcs_reconstruction_optimal(s1, s2):
    memo = {}

    def lcs_rec(i1, i2):
        if i1 == len(s1) or i2 == len(s2):
            return 0
        if (i1, i2) in memo:
            return memo[(i1, i2)]
        if s1[i1] == s2[i2]:
            memo[(i1, i2)] = 1 + lcs_rec(i1 + 1, i2 + 1)
        else:
            memo[(i1, i2)] = max(lcs_rec(i1 + 1, i2), lcs_rec(i1, i2 + 1))
        return memo[(i1, i2)]

    i1, i2 = 0, 0
    res = []

    while i1 < len(s1) and i2 < len(s2):
        if s1[i1] == s2[i2]:
            res.append(s1[i1])
            i1 += 1
            i2 += 1
        elif lcs_rec(i1 + 1, i2) > lcs_rec(i1, i2 + 1):
            i1 += 1
        else:
            i2 += 1

    return ''.join(res)

Reusable Idea: Solution Reconstruction

When a DP problem asks for the solution itself instead of only the value, there are usually two approaches:

1. Store full solutions in the memo table. This is straightforward but often expensive.
2. Store only values, then reconstruct the answer later by following one optimal path and repeatedly querying the value-based recurrence.

This technique is not specific to LCS. It is reusable across many DP problems.

Extra Credit: Tabulation

Tabulation starts with the same recurrence relation as memoization. The main difference is that we fill subproblems iteratively instead of recursively.

The critical question is iteration order. We must fill the table in an order that respects dependencies.

For Road Trip:

delay(i) = times[i] + min(delay(i + 1), delay(i + 2), delay(i + 3))

In tabulation form:

dp[i] = times[i] + min(dp[i + 1], dp[i + 2], dp[i + 3])

Because dp[i] depends on larger indices, we must iterate from right to left.

def delay(times):
    n = len(times)
    # Pad with 3 extra zeros to represent the base case: delay(i) = 0 for i >= n
    dp = [0] * (n + 3)

    for i in range(n - 1, -1, -1):
        dp[i] = times[i] + min(dp[i + 1], dp[i + 2], dp[i + 3])

    return min(dp[0], dp[1], dp[2])

Analysis:

• Subproblems: n
• Work per iteration: O(1)
• Total time: O(n)
• Extra space: O(n)

Rolling Array Optimization

Road Trip only reads the next three DP values at each step, so the full array is unnecessary.

def delay(times):
    n = len(times)
    # dp1, dp2, dp3 track delay(i+1), delay(i+2), delay(i+3)
    dp1 = dp2 = dp3 = 0

    for i in range(n - 1, -1, -1):
        cur = times[i] + min(dp1, dp2, dp3)
        dp1, dp2, dp3 = cur, dp1, dp2

    return min(dp1, dp2, dp3)

This reduces the extra space from O(n) to O(1) without changing the time complexity.

Key Takeaways

• Start dynamic programming by writing down a recurrence relation.
• DP is especially common in optimization and counting problems.
• If the brute-force solution is backtracking and the same smaller inputs keep reappearing, you probably have overlapping subproblems.
• Memoization is often the most intuitive way to implement a recurrence relation.
• Tabulation can unlock rolling-array space optimizations. (The Climbing Stairs problem is a classic example of this).
• Returning the value of a solution is often easier than returning the solution itself.

Dynamic programming does not work for every problem. If the choices already made change the nature of the remaining work too much, subproblems may stop overlapping and DP becomes much less useful.