Dynamic programming

Stop recomputing the same answer. DP is recursion plus a memory: caching each subproblem collapses an exponential tree into a polynomial DAG. Almost every hard interview is a DP in disguise, which is why this is the file to internalise.

Why this paradigm (the single most important file)

Dynamic Programming is what you reach for when a problem has a recursive structure (like backtracking, lesson 13) but the recursion tree revisits the same subproblem over and over. Caching each subproblem's answer collapses an exponential tree into a polynomial DAG. DP is not a trick; it is "recursion + remember the answers."

Two properties a problem must have for DP

1. Optimal substructure — the optimal answer to the whole is built from optimal answers to subproblems. (e.g. the shortest path to node N uses the shortest paths to N's predecessors.) If a globally optimal solution can be assembled from locally optimal pieces, you have it.
2. Overlapping subproblems — the naive recursion solves the same subproblem many times. fib(n) recomputes fib(n-2) ~fib(n) times. (If subproblems are all distinct, like merge sort, it's divide-and-conquer, not DP.)

Optimal substructure says DP is correct; overlapping subproblems says DP is necessary (otherwise plain recursion is fine). You need both.

How to find the recurrence — the checklist for EVERY DP

Recognizing DP in an interview

• "Count the number of ways ...", "min/max cost to ...", "longest/shortest ... such that ...", "is it possible to ...".
• Choices at each step, and future choices depend only on a small summary of the past (the state), not the entire history.
• A greedy guess gives wrong answers on small examples (so it's not lesson 15).
• Backtracking would work but is too slow because branches recompute.

The same problem, three ways: climbing stairs / Fibonacci

Climbing stairs(n) = ways to reach step n taking 1 or 2 steps = fib(n+1). State dp[i] = ways to reach step i; transition dp[i] = dp[i-1] + dp[i-2]. We show the same problem through all three stages of the progression so the transformation is concrete.

(a) Memoization / top-down

Natural recursion + a cache. lru_cache turns the exponential tree into O(n) distinct calls. This is the easiest version to derive in an interview — write the recurrence, slap on @lru_cache. It solves only the subproblems you actually reach.

from functools import lru_cache

def climb_top_down(n: int) -> int:
    @lru_cache(maxsize=None)
    def ways(i: int) -> int:
        if i <= 1:               # BASE CASE: 1 way to be at step 0 or 1
            return 1
        return ways(i - 1) + ways(i - 2)   # TRANSITION
    return ways(n)

(b) Tabulation / bottom-up

Fill dp[0..n] in increasing order so each entry's dependencies (i-1, i-2) are already computed. No recursion → no stack limit. The dependency order here is simply "small i before large i."

def climb_bottom_up(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1            # BASE CASES
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]      # TRANSITION, in dependency order
    return dp[n]                 # ANSWER

(c) Space optimization

dp[i] depends only on the previous two values, so we keep two rolling variables instead of the whole table. This O(1)-space trick applies to any DP whose transition reaches back a fixed number of cells.

def climb_optimized(n: int) -> int:
    a, b = 1, 1                  # a = dp[i-2], b = dp[i-1]
    for _ in range(2, n + 1):
        a, b = b, a + b          # slide the window forward one step
    return b

1D DP family

House robber — LeetCode 198

Max sum of non-adjacent elements. State dp[i] = max loot considering houses 0..i. Transition: rob i (nums[i] + dp[i-2]) or skip i (dp[i-1]); take the max — the "last choice" framing is "did we rob house i or not?" Space-optimized to two rolling variables.

def house_robber(nums: List[int]) -> int:
    prev2, prev1 = 0, 0          # max loot up to i-2 and i-1
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)   # skip vs rob
    return prev1

Coin change — LeetCode 322

Fewest coins to make amount; -1 if impossible (coins reusable). Greedy fails here — see lesson 15. State dp[a] = min coins to make amount a. Transition dp[a] = 1 + min(dp[a - c]) over coins c <= a. Base dp[0] = 0. Order: a from 0 upward (dp[a-c] is smaller, computed earlier).

def coin_change(coins: List[int], amount: int) -> int:
    INF = float("inf")
    dp = [0] + [INF] * amount    # dp[0]=0, rest unknown
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1        # TRANSITION
    return dp[amount] if dp[amount] != INF else -1

Word break — LeetCode 139

Can s be segmented into dictionary words? State dp[i] = can s[:i] be fully segmented? Transition dp[i] = True if some j<i has dp[j] and s[j:i] in dict. Base dp[0] = True (empty prefix is trivially segmentable). Answer dp[len(s)].

def word_break(s: str, word_dict: List[str]) -> bool:
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:    # a valid split point
                dp[i] = True
                break
    return dp[n]

2D grid DP family

Unique paths — LeetCode 62

Paths from top-left to bottom-right moving only right/down on an m×n grid. State dp[i][j] = #paths to reach cell (i,j). Transition dp[i][j] = dp[i-1][j] + dp[i][j-1] (arrived from above or left). Base: first row & column = 1. Space-optimized to a single row — each cell needs the row above (its old value) plus the cell to its left (already updated).

def unique_paths(m: int, n: int) -> int:
    row = [1] * n                # represents the top row (all 1s)
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1] # row[j]=from above (old) + row[j-1]=from left
    return row[n - 1]

Minimum path sum — LeetCode 64

Cheapest top-left → bottom-right path, moving right/down, summing cell values. State dp[i][j] = min cost to reach (i,j). Transition dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Done in place to use O(1) extra space.

def min_path_sum(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            up = grid[i - 1][j] if i > 0 else float("inf")
            left = grid[i][j - 1] if j > 0 else float("inf")
            grid[i][j] += min(up, left)      # TRANSITION
    return grid[m - 1][n - 1]

String DP family

Longest common subsequence — LeetCode 1143

Length of the longest subsequence present in both strings — the archetypal 2D string DP. State dp[i][j] = LCS of a[:i] and b[:j]. Transition: if the last characters match, extend (1 + dp[i-1][j-1]); else take the better of dropping one character from either side. Base dp[0][*] = dp[*][0] = 0 (an empty string shares nothing).

def longest_common_subsequence(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Edit distance — LeetCode 72 (Levenshtein)

Min insert/delete/replace ops to turn a into b. State dp[i][j] = min edits to turn a[:i] into b[:j]. If the last characters match it's a no-op; otherwise it's 1 + the cheapest of three moves:

Base dp[i][0] = i (delete all), dp[0][j] = j (insert all).

def edit_distance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],      # delete
                                   dp[i][j - 1],      # insert
                                   dp[i - 1][j - 1])  # replace
    return dp[m][n]

Knapsack family

Partition equal subset sum — LeetCode 416

Can nums be split into two equal-sum halves? Equivalent to 0/1 knapsack: can we hit target = total/2 using each number at most once? State dp[t] = is subset-sum t achievable? Transition: for each num, dp[t] |= dp[t - num]. Iterate t downward so each item is used at most once — the hallmark of 0/1 knapsack (going upward would allow reuse, which is the unbounded variant).

def can_partition_subset_sum(nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 == 1:
        return False                 # odd total can't split evenly
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for t in range(target, num - 1, -1):     # DOWNWARD -> 0/1 (no reuse)
            if dp[t - num]:
                dp[t] = True
    return dp[target]

0/1 knapsack

Max value of items fitting in capacity, each item taken 0 or 1 times — the framing every weighted-selection DP reduces to. State dp[w] = best value with total weight ≤ w. Transition dp[w] = max(dp[w], dp[w - wt] + val), w downward. Recognizing this family means many problems (including LCS, a "pick or skip per index" DP) collapse to one template.

def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for wt, val in zip(weights, values):
        for w in range(capacity, wt - 1, -1):     # DOWNWARD -> each item once
            if dp[w - wt] + val > dp[w]:
                dp[w] = dp[w - wt] + val
    return dp[capacity]

Longest increasing subsequence — O(n²) and O(n log n)

LeetCode 300. The O(n²) DP: state dp[i] = length of the longest increasing subsequence ending at i; transition dp[i] = 1 + max(dp[j]) over j<i with nums[j] < nums[i]. Answer max(dp) — the LIS can end anywhere, so the answer is not dp[n-1].

def lis_n2(nums: List[int]) -> int:
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
    return max(dp)

The O(n log n) patience-sorting version. Insight: maintain tails, where tails[k] = smallest possible tail of an increasing subsequence of length k+1. For each x, binary-search the first tail ≥ x and overwrite it (or append if x is biggest so far). Keeping tails as small as possible leaves the most room for future extensions. The length of tails at the end is the LIS length — note tails is not the LIS itself.

from bisect import bisect_left

def lis_nlogn(nums: List[int]) -> int:
    tails: List[int] = []
    for x in nums:
        i = bisect_left(tails, x)        # first position with tails[i] >= x
        if i == len(tails):
            tails.append(x)              # x extends the longest chain
        else:
            tails[i] = x                 # x makes a length-(i+1) chain "lower"
    return len(tails)

Interval DP — matrix chain multiplication

Matrix i has dimensions dims[i] x dims[i+1]; find the min scalar multiplications to multiply the whole chain, choosing where to parenthesize. Recognize the interval-DP shape: the state is a range dp[i][j], and the transition tries every split point k inside the range, combining two sub-ranges. You must fill short ranges before long ones (iterate by length), because dp[i][j] depends on strictly smaller sub-intervals. Other members: burst balloons, optimal BST, palindrome range DPs.

def matrix_chain_order(dims: List[int]) -> int:
    n = len(dims) - 1                    # number of matrices
    if n < 2:
        return 0
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):       # ORDER: increasing interval length
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):        # try every split point
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n - 1]