Contents

How to Analyze DP Problems

For fast and reliable DP design:

  1. Define state
    dp[state] must represent one precise subproblem.

  2. Write transition
    Express current answer using smaller states.

  3. Determine order
    Top-down (memo DFS) or bottom-up (iteration).

  4. Base cases + invalid states
    Missing this is the most common source of bugs.

  5. Space optimization
    If transition only uses previous row/column, compress dimensions.

1D DP (knapsack/linear)

def knap01(wt: list[int], val: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]
ID Title Link
322 Coin Change Coin Change
139 Word Break Word Break

2D DP (grid/path)

def unique_paths_with_obstacles(g: list[list[int]]) -> int:
    m, n = len(g), len(g[0])
    if g[0][0] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if g[i][j] == 1:
                dp[i][j] = 0
                continue
            if i > 0:
                dp[i][j] += dp[i - 1][j]
            if j > 0:
                dp[i][j] += dp[i][j - 1]
    return dp[m - 1][n - 1]
ID Title Link
62 Unique Paths Unique Paths
63 Unique Paths II Unique Paths II
221 Maximal Square Maximal Square

Digit DP (count numbers with property)

from functools import lru_cache


def count_without_adjacent_equal_digits(N: int) -> int:
    s = str(N)

    @lru_cache(maxsize=None)
    def dfs(i: int, prev: int, tight: bool, started: bool) -> int:
        if i == len(s):
            return 1 if started else 0

        res = 0
        lim = int(s[i]) if tight else 9
        for d in range(lim + 1):
            nt = tight and (d == lim)
            ns = started or (d != 0)
            if not ns or prev == -1 or d != prev:
                res += dfs(i + 1, d if ns else prev, nt, ns)
        return res

    return dfs(0, -1, True, False)
ID Title Link
233 Number of Digit One Number of Digit One
902 Numbers At Most N Given Digit Set Numbers At Most N Given Digit Set
1012 Numbers With Repeated Digits Numbers With Repeated Digits

Bitmask DP (TSP / subsets)

def tsp_min_cycle_cost(w: list[list[int]]) -> int:
    n = len(w)
    INF = 10**18
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at node 0

    for mask in range(1, 1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            for v in range(n):
                if (mask >> v) & 1:
                    continue
                nm = mask | (1 << v)
                dp[nm][v] = min(dp[nm][v], dp[mask][u] + w[u][v])

    full = (1 << n) - 1
    return min(dp[full][u] + w[u][0] for u in range(n))
ID Title Link
847 Shortest Path Visiting All Nodes Shortest Path Visiting All Nodes
698 Partition to K Equal Sum Subsets Partition to K Equal Sum Subsets