Dynamic Programming: 5 Universal Problem-Solving Templates

DP is the highest-signal topic in algorithm interviews. Core idea: split large problem into overlapping subproblems, store intermediate results to avoid recomputation. Master 5 steps + 5 templates to solve 90% of DP problems.

Universal Five Steps + Knapsack Family

Five steps: (1) Define what dp[i][j] means. (2) Derive transitions by considering last binary choice. (3) Init base cases. (4) Determine correct for-loop order. (5) Apply rolling-array space optimization. 0/1 Knapsack iterates capacity backwards (one item each); Unbounded iterates forwards.

from functools import lru_cache
from typing import List
import bisect

def t1_01_knapsack(cap: int, ws: List[int], vs: List[int]) -> int:
    n = len(ws); dp = [0] * (cap + 1)
    for i in range(n):
        for c in range(cap, ws[i] - 1, -1):
            dp[c] = max(dp[c], dp[c - ws[i]] + vs[i])
    return dp[cap]

def t2_unbounded_knapsack(cap: int, ws: List[int], vs: List[int]) -> int:
    dp = [0] * (cap + 1)
    for c in range(1, cap + 1):
        for i, w in enumerate(ws):
            if w <= c: dp[c] = max(dp[c], dp[c - w] + vs[i])
    return dp[cap]

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

def t4_lis(nums: List[int]) -> int:
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

def t5_interval_palindrome_cuts(s: str) -> int:
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = s[i] == s[j] and (j - i < 3 or is_pal[i + 1][j - 1])
    cut = [float('inf')] * n
    for j in range(n):
        if is_pal[0][j]: cut[j] = 0
        else:
            for i in range(1, j + 1):
                if is_pal[i][j]: cut[j] = min(cut[j], cut[i - 1] + 1)
    return int(cut[n - 1])

if __name__ == "__main__":
    print(t1_01_knapsack(10, [2, 3, 5, 7], [3, 4, 6, 10]))
    print(t3_lcs("abcde", "aceb"), t4_lis([10, 9, 2, 5, 3, 7, 101, 18]))
    print(t5_interval_palindrome_cuts("aabcbdadcb"))

Subsequence / Interval / Bitmask / Tree DP

For two-string subsequence, dp[i][j] encodes first i chars vs first j. Interval DP enumerates by interval length (palindromes/games/stones). Bitmask tracks visited set (TSP). Tree DFS returns two states per child (picked / not-picked).

Best Practices

If transitions feel mysterious, start with brute recursion + memoization and draw the recursion tree. Once you see the shape of overlapping subproblems, convert to bottom-up iterative. Pass samples first; optimize space only when logic is rock solid.