Dynamic programming cheat sheet

Ways to cross n stepping stones, one or two at a time

From k stones left, your first move leaves k - 1 or k - 2, so ways(k) = ways(k - 1) + ways(k - 2), with ways(0) = ways(1) = 1. Plain recursion repeats the same sub-questions and grows exponentially; caching each answer makes it O(n) time and O(n) memory. A loop with two variables brings memory to O(1).

def stone_ways(n: int) -> int:
    known: dict[int, int] = {}  # memo: stone -> ways from there

    def ways(k: int) -> int:
        if k <= 1:
            return 1  # zero or one stone left: one way
        if k not in known:
            known[k] = ways(k - 1) + ways(k - 2)
        return known[k]

    return ways(n)

Fewest coins to make an amount

Let need[a] be the fewest coins for amount a, with need[0] = 0. For each a, try every coin c ≤ a: need[a] = min(need[a - c] + 1). Fill a from 1 upward so the smaller amounts are ready. O(amount × coins) time, O(amount) memory. Greedy 'largest coin first' fails for values like [1, 3, 4] and amount 6.

import math


def fewest_coins(coins: list[int], amount: int) -> int:
    need = [0] + [math.inf] * amount  # need[a]: fewest coins for a
    for total in range(1, amount + 1):  # smaller totals are ready
        for coin in coins:
            if coin <= total and need[total - coin] + 1 < need[total]:
                need[total] = need[total - coin] + 1
    best = need[amount]
    return -1 if best == math.inf else int(best)

Fewest edits to turn one word into another

Let cost[i][j] be the edits needed to turn the first i letters of the source into the first j letters of the target. Empty prefixes cost i + j. If the current letters match, cost[i][j] = cost[i - 1][j - 1]; otherwise it is 1 plus the cheapest of delete (up), insert (left) or replace (diagonal). Fill row by row: O(m × n) time and O(m × n) memory for the full table, as here; keeping only two rows cuts memory to O(n) when you need just the number.

def fewest_edits(src: str, dst: str) -> int:
    # cost[i][j]: edits to turn src[:i] into dst[:j]
    cost = [[i + j if i == 0 or j == 0 else 0
             for j in range(len(dst) + 1)] for i in range(len(src) + 1)]
    for i, a in enumerate(src, 1):
        for j, b in enumerate(dst, 1):
            if a == b:
                cost[i][j] = cost[i - 1][j - 1]  # letters match: free
            else:
                cost[i][j] = 1 + min(cost[i - 1][j],  # delete a
                                     cost[i][j - 1],  # insert b
                                     cost[i - 1][j - 1])  # swap a for b
    return cost[-1][-1]

Best haul without opening two neighbouring lockers

For each locker, either skip it (keep the best so far) or open it (its amount plus the best up to two lockers back). Two running values are enough: best through the previous locker and best through the one before. O(n) time and O(1) memory.

def best_haul(amounts: list[int]) -> int:
    two_back = one_back = 0  # best totals two and one lockers ago
    for a in amounts:
        two_back, one_back = one_back, max(one_back, two_back + a)
    return one_back

Best haul when the lockers form a ring

In a ring, the first and last lockers cannot both be opened. So solve the straight-row version twice, once without the first locker and once without the last, and take the better result. Each run is O(n), so the total is O(n) time. The two slices take O(n) memory; passing index bounds instead of slices brings it to O(1).

def ring_haul(amounts: list[int]) -> int:
    def straight(row: list[int]) -> int:
        two_back = one_back = 0
        for a in row:
            two_back, one_back = one_back, max(one_back, two_back + a)
        return one_back

    if len(amounts) == 1:
        return amounts[0]
    return max(straight(amounts[1:]), straight(amounts[:-1]))

Ways to read a digit string as letters (1 = A … 26 = Z)

Let ways[i] count the readings of the first i digits. The last letter used either one digit (valid if it is not '0') or two digits (valid if they form 10 to 26). So ways[i] = (ways[i - 1] if one-digit is valid) + (ways[i - 2] if two-digit is valid), with ways[0] = 1. Two rolling values give O(n) time and O(1) memory.

def readings(digits: str) -> int:
    before, last = 0, 1  # readings of the prefix two back and one back
    for i, d in enumerate(digits):
        here = last if d != "0" else 0  # d read as one letter
        if i and 10 <= int(digits[i - 1:i + 1]) <= 26:
            here += before  # the pair read as one letter
        before, last = last, here
    return last

Can a string be split into dictionary words?

Let ok[i] mean the first i characters can be split. ok[0] is True. For each i, check each allowed word length L: if ok[i - L] holds and the slice of length L ending at i is an allowed word, ok[i] is True. With W distinct word lengths and words up to L long, that is O(n · W · L) time and O(n) memory.

def can_split(text: str, words: list[str]) -> bool:
    allowed = set(words)
    lengths = {len(w) for w in allowed}
    ok = [True] + [False] * len(text)  # ok[i]: text[:i] splits
    for i in range(1, len(text) + 1):
        for size in lengths:
            start = i - size
            if start >= 0 and ok[start] and text[start:i] in allowed:
                ok[i] = True
                break
    return ok[-1]

Longest rising sequence of picks from a list

The O(n²) DP sets best[i] = 1 + the largest best[j] for j < i with a smaller value. The faster method keeps tails[k] = the smallest possible last value of a rising pick of length k + 1. For each value, binary search the first tail that is not smaller and replace it, or append if none. The length of tails is the answer: O(n log n) time, with O(n) space for tails.

from bisect import bisect_left


def longest_rising(values: list[int]) -> int:
    tails: list[int] = []  # tails[k]: smallest end of a rise of k + 1
    for v in values:
        k = bisect_left(tails, v)
        if k == len(tails):
            tails.append(v)  # v extends the longest rise
        else:
            tails[k] = v  # v is a smaller end for that length
    return len(tails)

Longest shared subsequence of two strings

Let best[i][j] be the answer for the first i letters of one string and the first j of the other. If the current letters match, best[i][j] = best[i - 1][j - 1] + 1; otherwise take the larger of dropping one letter from either side. O(m × n) time; two rows give O(n) memory.

def shared_subseq(a: str, b: str) -> int:
    above = [0] * (len(b) + 1)  # previous row of the table
    for x in a:
        here = [0]
        for j, y in enumerate(b, 1):
            if x == y:
                here.append(above[j - 1] + 1)  # extend the match
            else:
                here.append(max(above[j], here[j - 1]))
        above = here
    return above[-1]

Routes across a grid with blocked cells

Each open cell can be entered only from above or from the left, so routes[r][c] = routes[r - 1][c] + routes[r][c - 1], and blocked cells hold 0. The start holds 1 unless it is blocked. Fill row by row: O(R × C) time, and one row of memory, O(C), is enough.

def count_routes(grid: list[list[int]]) -> int:
    row = [0] * len(grid[0])  # routes into each column, this row
    row[0] = 1
    for cells in grid:
        for c, blocked in enumerate(cells):
            if blocked:
                row[c] = 0  # nothing passes through a block
            elif c:
                row[c] += row[c - 1]  # from above (old) + from left
    return row[-1]

Cheapest route from top-left to bottom-right

The cheapest way into a cell comes from the cheaper of the cell above and the cell to its left, so cost[r][c] = grid[r][c] + min(above, left). The first row and column have only one way in. O(R × C) time, one row of memory: O(C).

import math


def cheapest_route(grid: list[list[int]]) -> int:
    row = [math.inf] * len(grid[0])  # cheapest cost into each column
    row[0] = 0
    for cells in grid:
        for c, cost in enumerate(cells):
            from_left = row[c - 1] if c else math.inf
            row[c] = cost + min(row[c], from_left)
    return int(row[-1])

Split items into two piles of equal weight

If the total is odd, it is impossible. Otherwise ask whether some items add up to half the total. Keep the set of totals reachable so far; for each weight, add it to every reachable total (going from the old set so each item is used once). Stop early when half is reached. O(n × S) time for total S, O(S) memory.

def equal_piles(weights: list[int]) -> bool:
    total = sum(weights)
    if total % 2:
        return False  # an odd total cannot split evenly
    half = total // 2
    reach = {0}  # totals some items add up to
    for w in weights:
        reach |= {t + w for t in reach if t + w <= half}
        if half in reach:
            return True
    return half in reach

Number of ways to pay an amount with unlimited coins

Let ways[a] count combinations for amount a, with ways[0] = 1. Process one coin value at a time, and for each, sweep amounts upward adding ways[a - c]. Because coins are the outer loop, each combination is built in one fixed coin order and counted once. O(amount × coins) time, O(amount) memory.

def pay_ways(coins: list[int], amount: int) -> int:
    ways = [1] + [0] * amount  # one way to pay 0: no coins
    for c in coins:  # one coin value at a time: no reorderings
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

Largest product of a contiguous run

Track both the largest and the smallest product of a run ending at each position, because a negative value turns the smallest into the largest. At each value v, the new largest is the max of v, v × old largest and v × old smallest; likewise for the smallest. O(n) time, O(1) memory.

def best_product(vals: list[int]) -> int:
    high = low = best = vals[0]  # extremes of runs ending here
    for v in vals[1:]:
        options = (v, high * v, low * v)
        high, low = max(options), min(options)  # a negative swaps them
        best = max(best, high)
    return best

Dynamic programming in four steps

Work in four steps. 1) State: say in words what one cell means, such as 'fewest coins for amount a'. 2) Transition: how a cell is built from smaller cells. 3) Base cases: the cells you know without computing. 4) Order: fill cells so everything a cell needs is ready. Then the cost is states × work per state, and you can look for memory savings.

Top-down caching or bottom-up tables?

Top-down writes the natural recursion and caches results, computing only the states actually reached; it is quickest to write but uses the call stack. Bottom-up fills a table in a fixed order with loops; it avoids recursion limits and makes memory savings like rolling rows easy. Both have the same time complexity for the same states.

Saving memory with rolling rows

If each row reads only the row before it, keep two rows (previous and current) instead of the whole table: O(columns) memory. Often one row works if you fill it in the right direction: left to right when a cell needs the new left neighbour, right to left when it needs the old value to its left (as in 0/1 knapsack). The catch is that you can no longer walk back to rebuild the answer.

How to tell a problem needs DP

Look for three things: you make a sequence of choices, the question asks for a best value or a count over all choices, and different choice sequences lead to the same sub-question. If a simple local rule always works (with a proof), greedy is enough. If you must list every answer, backtracking is needed. If sub-questions repeat, cache them: that is DP.