Dynamic Programming

DP applies when a problem has overlapping subproblems and optimal substructure. Memoisation (top-down) keeps the natural recursive shape and computes only the states actually reachable — better for sparse state spaces, but it costs stack depth.

from functools import cache

@cache                          # memoisation, top-down
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

def fib_tab(n):                 # tabulation, bottom-up
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

def fib_opt(n):                 # O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# state: dp[i] = the i-th Fibonacci number
# transition: dp[i] = dp[i-1] + dp[i-2]
# complexity = states * transition cost = n * O(1)

One-dimensional DP indexes state by position, with transitions reaching back a fixed distance. The canonical family: climbing stairs (dp[i] = dp[i−1] + dp[i−2]), house robber (dp[i] = max(dp[i−1], dp[i−2] + a[i]) — the constraint forces the skip), max subarray/Kadane (dp[i] = max(a[i], dp[i−1] + a[i])), and jump games.

def climb(n):                     # dp[i] = ways to reach step i
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

def rob(a):                       # cannot rob adjacent houses
    prev = cur = 0
    for v in a:
        prev, cur = cur, max(cur, prev + v)
    return cur

def max_subarray(a):              # Kadane: extend or restart
    best = cur = a[0]
    for v in a[1:]:
        cur = max(v, cur + v)
        best = max(best, cur)
    return best

# state: dp[i] = best answer ENDING at i
# transition looks back a FIXED distance -> O(1) space

dp[i][w] is the best value using the first i items within capacity w, with the transition dp[i][w] = max(dp[i−1][w], value[i] + dp[i−1][w − weight[i]]) — skip or take. Complexity is O(nW), which is PSEUDO-polynomial: it is polynomial in the numeric value of W, not in its bit length, so a huge capacity is genuinely expensive and the problem remains NP-hard.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):     # DESCENDING!
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]

# ascending would allow reusing the same item
# => that is the UNBOUNDED knapsack

def knapsack_2d(weights, values, W):       # keeps choices
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wt, val = weights[i-1], values[i-1]
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]                       # skip
            if w >= wt:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - wt] + val)   # take
    return dp

# O(nW) — pseudo-polynomial, NOT polynomial in input size

Unbounded knapsack allows unlimited copies, so the 1D loop runs ASCENDING — dp[w] may legitimately reuse the current item. Two distinct problems share this shape and must not be confused: MINIMUM coins (dp[amount] = min over coins of dp[amount − c] + 1, initialised to infinity) and COUNTING combinations (dp[amount] += dp[amount − c]).

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):     # ASCENDING = reuse
            dp[a] = min(dp[a], dp[a - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

def count_combinations(coins, amount):     # unordered
    dp = [1] + [0] * amount
    for c in coins:                        # coins OUTER
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

def count_permutations(coins, amount):     # ordered
    dp = [1] + [0] * amount
    for a in range(1, amount + 1):         # amount OUTER
        for c in coins:
            if a >= c:
                dp[a] += dp[a - c]
    return dp[amount]

dp[i][j] is the LCS length of the first i characters of A and first j of B. If A[i−1] == B[j−1] then dp[i][j] = dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).

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

def lcs_string(a, b):
    dp = lcs_table(a, b)
    i, j, out = len(a), len(b), []
    while i and j:                     # walk back from corner
        if a[i-1] == b[j-1]:
            out.append(a[i-1]); i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

# longest common SUBSTRING differs by one line:
#   else: dp[i][j] = 0          # contiguity broken

Levenshtein distance: dp[i][j] = dp[i−1][j−1] if the characters match, else 1 + min(dp[i−1][j−1] replace, dp[i−1][j] delete, dp[i][j−1] insert). O(nm) time, O(min(n,m)) space for the value alone.

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i      # delete all
    for j in range(m + 1): dp[0][j] = j      # insert all

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]      # free
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],            # replace
                    dp[i-1][j],              # delete
                    dp[i][j-1])              # insert
    return dp[n][m]

edit_distance("kitten", "sitting")   # 3

# Damerau adds transposition:
#   if a[i-1]==b[j-2] and a[i-2]==b[j-1]:
#       dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)

The O(n²) DP is dp[i] = 1 + max(dp[j]) over j < i with a[j] < a[i]. The O(n log n) method maintains an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1; for each element, binary search for the first tail ≥ it and replace, or append.

from bisect import bisect_left

def lis_length(a):
    tails = []
    for v in a:
        i = bisect_left(tails, v)      # strictly increasing
        if i == len(tails):
            tails.append(v)            # extends the LIS
        else:
            tails[i] = v               # tighter tail
    return len(tails)

# tails is sorted, so binary search is valid.
# tails is NOT the LIS itself — only its LENGTH is right.

def lis_dp(a):                         # O(n^2), gives the path
    n = len(a)
    dp, prev = [1] * n, [-1] * n
    for i in range(n):
        for j in range(i):
            if a[j] < a[i] and dp[j] + 1 > dp[i]:
                dp[i], prev[i] = dp[j] + 1, j
    return max(dp)

Grid DP indexes state by coordinates, with transitions from a fixed set of neighbours determined by the allowed moves. Because rows depend only on the previous row, space collapses from O(nm) to O(m) — and to O(1) extra if you overwrite the input in place.

def unique_paths(grid):                 # 1 = blocked
    n, m = len(grid), len(grid[0])
    dp = [0] * m
    dp[0] = 1
    for i in range(n):
        for j in range(m):
            if grid[i][j]:
                dp[j] = 0                  # obstacle
            elif j > 0:
                dp[j] += dp[j-1]           # from the left
    return dp[-1]                          # O(m) space

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

# four-directional movement => cycles => use Dijkstra / 0-1 BFS

Tree DP computes dp[node] from dp[children] via post-order DFS, in O(n) because each node and edge is processed once. Multi-state variants are the norm: dp[node][0/1] for "node not taken / taken" solves maximum independent set on a tree (the tree version of house robber) and minimum vertex cover.

import sys
sys.setrecursionlimit(300000)

def max_independent_set(tree, root=0):
    # dp[node] = (best excluding node, best including node)
    def dfs(u, parent):
        excl, incl = 0, value[u]
        for v in tree[u]:
            if v == parent:
                continue
            ce, ci = dfs(v, u)
            excl += max(ce, ci)   # child free to do either
            incl += ce            # child must be excluded
        return excl, incl
    return max(dfs(root, -1))

def diameter(tree, root=0):
    best = 0
    def depth(u, parent):
        nonlocal best
        top2 = [0, 0]
        for v in tree[u]:
            if v == parent: continue
            d = depth(v, u) + 1
            top2 = sorted(top2 + [d])[-2:]   # two deepest
        best = max(best, top2[0] + top2[1])
        return top2[1]
    depth(root, -1)
    return best

Bitmask DP encodes a subset as an integer, giving O(2^n) states. The archetype is Held-Karp for travelling salesman: dp[mask][i] is the cheapest route visiting exactly the set mask and ending at i, giving O(2^n · n²) — exponential, but a vast improvement on O(n!) and practical to about n = 20.

from functools import cache

def tsp(dist):                       # Held-Karp
    n = len(dist)
    FULL = (1 << n) - 1

    @cache
    def go(mask, i):                 # visited=mask, at city i
        if mask == FULL:
            return dist[i][0]        # return home
        best = float("inf")
        for j in range(n):
            if mask >> j & 1:
                continue             # already visited
            best = min(best, dist[i][j] + go(mask | 1 << j, j))
        return best

    return go(1, 0)                  # O(2^n * n^2)

# assignment: popcount gives the row for free
def assign(cost):
    n = len(cost)
    @cache
    def go(mask):
        i = bin(mask).count("1")     # which task we are on
        if i == n:
            return 0
        return min(cost[i][j] + go(mask | 1 << j)
                   for j in range(n) if not mask >> j & 1)
    return go(0)