Dynamic Programming

Type: Algorithm Paradigm | LeetCode problems: 500+

---

Core Concepts

Optimal substructure — the optimal solution to a problem can be constructed from optimal solutions to its subproblems. Necessary condition for DP to be valid; if absent, greedy or brute force may be required.

Overlapping subproblems — the same subproblems are solved repeatedly during recursion. Caching (memoization) or pre-computation (tabulation) converts exponential recursion into polynomial time by solving each subproblem exactly once.

State — a minimal description of a subproblem such that the answer depends only on the state, not on how it was reached. Defining states correctly is the core skill; wrong state definition produces wrong or exponential-size DP.

Recurrence relation (transition) — an equation expressing the answer to a state in terms of answers to smaller states. The recurrence is the algorithm; everything else is bookkeeping.

Base case — states small enough to answer directly without further recursion. Every correct DP has at least one base case; missing it causes infinite recursion or wrong answers.

Subproblem DAG — the implicit directed acyclic graph where nodes are states and edges are dependencies. Bottom-up DP traverses this DAG in topological order; top-down traversal is driven by recursion.

Memoization — top-down approach; solve states recursively, cache each result the first time. Natural when the recursion structure is clear but not all states are reached.

Tabulation — bottom-up approach; fill a table in dependency order without recursion. Avoids stack overflow risk and often has better constant factors.

State space — the set of all distinct states. Its size determines time and space complexity (before any optimization).

Push vs pull transitions — pull: state i reads from previously computed states ("what can I come from?"). Push: computed state i writes to dependent states ("what can I contribute to?"). Push is useful for counting problems where future states are easier to enumerate.

---

Internal Representation

Direction matters for rolling arrays: in 0/1 knapsack, iterating capacity right-to-left prevents an item from being used twice in the same pass; iterating left-to-right gives unbounded knapsack.

---

Types / Variants

---

Key Algorithms

Fibonacci / Linear Recurrence

Compute dp[i] from the previous k values. O(n) time, O(k) space (rolling).
Key insight: only the last k values matter; rolling eliminates the full array.

Kadane's Algorithm — Maximum Subarray Sum

dp[i] = max subarray ending at index i. Transition: dp[i] = max(a[i], dp[i-1] + a[i]). O(n) time, O(1) space.
Key insight: if dp[i-1] < 0, starting fresh at a[i] is better than extending.

Longest Increasing Subsequence (LIS)

dp[i] = length of LIS ending at index i. O(n²) with quadratic transition; O(n log n) with patience sorting / binary search on a maintained tails array.
Key insight (O(n log n)): maintain tails[k] = smallest tail of all increasing subsequences of length k+1; binary search for insertion point.

import bisect
tails = []
for x in nums:
    pos = bisect.bisect_left(tails, x)
    if pos == len(tails): tails.append(x)
    else: tails[pos] = x

Longest Common Subsequence (LCS)

dp[i][j] = LCS of a[:i] and b[:j]. Transition: if a[i-1]==b[j-1], dp[i][j] = dp[i-1][j-1]+1; else max(dp[i-1][j], dp[i][j-1]). O(nm) time and space; O(min(n,m)) with rolling.

Edit Distance (Levenshtein)

dp[i][j] = min edits to transform a[:i] to b[:j]. Three operations: insert (from dp[i][j-1]+1), delete (dp[i-1][j]+1), replace (dp[i-1][j-1] + (a[i-1]!=b[j-1])). O(nm).

0/1 Knapsack

dp[c] = max value with capacity c. Iterate items outer, capacity right-to-left inner. O(nW) time, O(W) space.
Key insight: right-to-left ensures item i is not used twice in one pass.

Unbounded Knapsack

Same as 0/1 but iterate capacity left-to-right so the same item can be picked multiple times. O(nW).

Coin Change — Minimum Coins

Unbounded knapsack variant. dp[amount] = min coins. Base: dp[0]=0, rest = infinity. Transition: dp[c] = min(dp[c], dp[c-coin]+1) for each coin. O(n·amount).

Coin Change — Number of Ways

dp[amount] = number of combinations. Iterate coins outer, amount inner (left-to-right) to count combinations without order; iterate amount outer, coins inner to count permutations. O(n·amount).

Matrix Chain Multiplication — Interval DP

dp[l][r] = min cost to multiply matrices l..r. Split at each k ∈ [l,r): dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost(l,k,r)). Fill by increasing interval length. O(n³).

Burst Balloons

dp[l][r] = max coins from bursting all balloons in (l,r) (exclusive boundaries are sentinel 1s). Key insight: think of k as the last balloon popped in [l,r], so boundaries l and r still exist when k is popped. O(n³).

Palindromic Substrings / Palindrome DP

dp[l][r] = whether s[l..r] is a palindrome. Transition: s[l]==s[r] and dp[l+1][r-1]. Fill by increasing length. O(n²) time and space. Manacher's algorithm solves longest palindromic substring in O(n).

See strings.md for Manacher's algorithm.

Minimum Palindrome Cuts

dp[i] = min cuts for s[:i]. Transition: dp[i] = min(dp[j] + 1) for all j < i where s[j..i-1] is palindrome. O(n²) with precomputed palindrome table.

Wildcard / Regex Matching

dp[i][j] = whether pattern p[:j] matches string s[:i]. Handle * (matches any sequence) and ?/. (matches one char). O(nm).

Distinct Subsequences

dp[i][j] = number of ways s[:i] contains t[:j] as a subsequence. O(nm).

Best Time to Buy and Sell Stock — State Machine DP

States: hold, cash (not holding). Transitions encode cooldown and transaction limits as additional state dimensions. The pattern generalises to any "mode-switching" problem.

Unique Paths / Grid DP

dp[i][j] = number of paths/min cost to reach (i,j). Transition from above and left. O(nm) time, O(n) space with rolling.

House Robber

dp[i] = max rob in first i houses. Transition: dp[i] = max(dp[i-1], dp[i-2] + a[i]). Circular variant: run twice (exclude first house, exclude last house). O(n) time, O(1) space.

Bitmask DP — Traveling Salesman Problem

dp[mask][v] = min cost to visit exactly the nodes in mask, ending at v. Transition: extend to unvisited nodes. O(2ⁿ · n²) time, O(2ⁿ · n) space. Feasible only for n ≤ 20.

Digit DP

State: (position, tight, ...accumulated_property...). tight = whether digits so far match the upper bound prefix (limits next digit choice). Transition iterates over next digit d ∈ [0, 9] (or [0, limit[pos]] if tight). Returns count of valid numbers from current position. O(positions · 2 · property_space).

Knapsack on Trees (Selecting Subtree Nodes)

Root the tree. dp[v][k] = max value using exactly k nodes from subtree rooted at v. Merge children one at a time using a "tree knapsack" merge in O(subtree_size²) total. O(n²) overall.

---

Advanced Techniques

Divide and Conquer DP Optimization

Solves: dp[i][j] = min over k < j of (dp[i-1][k] + cost(k,j)) when the optimal split point opt(i,j) is monotone: opt(i,j) ≤ opt(i,j+1).
Mechanism: For each layer i, recurse: to compute dp[i][mid], search k in [lo_opt, hi_opt]; then solve left and right halves with narrowed search ranges.
When to prefer: Cost function satisfies the monotone-opt property (verify or prove it); otherwise use plain O(n²) per layer.
Complexity: O(n log n) per DP layer vs O(n²) naive.

Convex Hull Trick (CHT) / Li Chao Tree

Solves: dp[i] = min over j < i of (dp[j] + b[j]*a[i]) — linear functions in a[i] parameterized by j.
Mechanism: Maintain a lower envelope of lines y = b[j]*x + dp[j]; query minimum at x = a[i]. Monotone queries + monotone slopes → pointer-based O(n). Non-monotone → Li Chao segment tree O(n log n).
When to prefer: Transition is a dot-product form; slope or query is monotone. CHT is faster than divide-and-conquer optimization and simpler when monotonicity holds.
Complexity: O(n) with double monotonicity; O(n log n) with Li Chao tree (non-monotone).

Knuth's Optimization

Solves: Interval DP dp[l][r] = min(dp[l][k] + dp[k+1][r] + w(l,r)) when w satisfies the quadrangle inequality and is monotone on intervals.
Mechanism: opt[l][r] (the minimizing k) satisfies opt[l][r-1] ≤ opt[l][r] ≤ opt[l+1][r]. Use this to restrict k-search per cell.
When to prefer: Standard interval DP (matrix chain, optimal BST, stone merge) where w is provably quadrangle-convex.
Complexity: O(n²) vs O(n³) naive.

Slope Trick

Solves: Problems on arrays where the DP value function is piecewise linear and convex (e.g., minimum cost to make array non-decreasing).
Mechanism: Represent the DP function by its slope change points (a priority queue of breakpoints). Transitions correspond to simple heap operations (push/pop/shift).
When to prefer: Cost is L1-type (sum of absolute differences); "make array satisfy monotone/equal property with min cost" problems.
Complexity: O(n log n) vs O(n²) standard DP.

Sum Over Subsets (SOS) DP

Solves: For each mask, compute f[mask] = sum/max/min of a[sub] for all subsets sub of mask.
Mechanism: Iterate over each bit dimension: dp[mask] += dp[mask ^ (1<<i)] for each set bit i, in O(n·2ⁿ).
When to prefer: Counting or optimizing over all subsets of a mask; Hamming-adjacency relationships. Avoid if only a few masks are queried (iterate subsets directly in O(3ⁿ) then).
Complexity: O(n·2ⁿ).

Monotonic Queue DP Optimization

Solves: dp[i] = min/max(dp[j]) + cost(i) for j ∈ [i-k, i-1] (sliding window of predecessors).
Mechanism: Maintain a deque of candidate j indices in monotone order; evict out-of-window indices from front; evict dominated indices from back.
When to prefer: Predecessor window has a fixed size or a constraint that makes the window slide; simpler than CHT when the function is not linear.
Complexity: O(n) vs O(nk) naive.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Wrong state definition — the most common error: state omits a necessary dimension (e.g., forgetting the "number of transactions" axis in stock problems). Consequence: different histories with different valid choices collapse to one state. Fix: ask "is the answer to this state unique given only this information?"

• Off-by-one in base cases — dp[0] vs dp[1] indexing; forgetting to initialize the empty-prefix base case separately from size-1. Common in LCS, edit distance, palindrome cuts. Always trace a 2×2 example manually.

• Overflow in counting — the number of ways can exceed int range even for moderate n. Use modular arithmetic (% MOD) at every addition step, not just at the end.

• Order of iteration in rolling array — 0/1 knapsack requires right-to-left capacity iteration; left-to-right gives unbounded knapsack. Swapping them silently changes the problem type.

• Bitmask out-of-bounds — 1 << n overflows 32-bit int when n ≥ 31; use 1 << n in Python (arbitrary precision) or cast to long in Java/C++.

• Interval DP: base case for length-1 vs length-2 — forgetting to handle even-length palindromes or length-2 intervals separately causes wrong initialization.

• Digit DP: "leading zeros" flag — numbers with leading zeros often have different digit-property semantics; track a started flag to suppress leading zeros.

• Memoization with mutable arguments — using a list or dict as a function argument and then caching by reference. Use tuples or freeze state before caching.

• Tree DP: treating undirected tree as graph — visiting parent again as a child causes infinite recursion or double-counting. Root the tree and pass parent to DFS, or use in-degree for topological iteration.

• Push DP forgetting initialization — when pushing dp[i] into dp[j], if dp[i] was never reached (still infinity), pushing its value corrupts dp[j]. Initialize unreachable states carefully.

---

Implementation Notes

• Python default recursion limit is 1000; for deep memoization use sys.setrecursionlimit(200000) or convert to bottom-up.
• functools.lru_cache(None) is simpler than a manual dict; use @cache (Python 3.9+) as shorthand.
• lru_cache does not work with unhashable arguments (lists, dicts); convert to tuples before passing.
• Python int is arbitrary precision so overflow is not a concern, but always apply % MOD for counting problems explicitly required by the problem.
• When reducing a 2D DP to a 1D rolling array, verify that the old and new iteration directions are correct — this is a frequent source of subtle bugs.
• For bitmask DP, iterating subsets of a mask in Python: sub = mask; while sub > 0: ...; sub = (sub - 1) & mask. This enumerates all subsets including 0 if sub = (sub-1)&mask; while sub != mask pattern is used.
• bisect.bisect_left / bisect.bisect_right are the standard tools for O(n log n) LIS; no need to implement binary search manually.
• Interval DP outer loop should iterate length from 2 to n, not left-to-right on l, to ensure subproblems are filled before they are used.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

1D Linear DP

• Climbing Stairs (LC 70) — Fibonacci base
• House Robber (LC 198) — include/exclude
• House Robber II (LC 213) — circular, two runs
• Maximum Subarray (LC 53) — Kadane's
• Jump Game II (LC 45) — greedy or DP
• Decode Ways (LC 91) — counting with constraints

Subsequences

• Longest Increasing Subsequence (LC 300) — O(n log n) required
• Russian Doll Envelopes (LC 354) — 2D LIS
• Number of Longest Increasing Subsequence (LC 673)
• Longest Common Subsequence (LC 1143) — 2D DP template
• Distinct Subsequences (LC 115) — counting LCS variant

Strings

• Edit Distance (LC 72) — must know cold
• Wildcard Matching (LC 44)
• Regular Expression Matching (LC 10) — harder variant
• Longest Palindromic Substring (LC 5) — Manacher's or expand-around-center
• Palindromic Substrings (LC 647)
• Minimum Cut Palindrome Partitioning (LC 132)

Knapsack / Combinatorics

• Coin Change (LC 322) — min coins
• Coin Change II (LC 518) — count ways
• Partition Equal Subset Sum (LC 416) — 0/1 knapsack boolean
• Target Sum (LC 494) — subset sum with signs
• Last Stone Weight II (LC 1049)

Grid DP

• Unique Paths (LC 62), Unique Paths II (LC 63)
• Minimum Path Sum (LC 64)
• Dungeon Game (LC 174) — reverse direction
• Cherry Pickup (LC 741, 1463) — two simultaneous paths

Interval DP

• Burst Balloons (LC 312) — classic "last element" trick
• Strange Printer (LC 664)
• Minimum Cost to Merge Stones (LC 1000)
• Palindrome Removal (LC 1246)

State Machine / Stock Problems

• Best Time to Buy and Sell Stock I–IV (LC 121, 122, 123, 188)
• Best Time to Buy and Sell Stock with Cooldown (LC 309)
• Best Time to Buy and Sell Stock with Transaction Fee (LC 714)

Bitmask DP

• Traveling Salesman / Shortest Path Visiting All Nodes (LC 847)
• Beautiful Arrangement (LC 526)
• Partition to K Equal Sum Subsets (LC 698)
• Minimum Cost to Connect Sticks / Huffman (LC 1167)

Tree DP

• House Robber III (LC 337) — tree rob
• Binary Tree Maximum Path Sum (LC 124)
• Diameter of Binary Tree (LC 543)
• Distribute Coins in Binary Tree (LC 979)

Digit DP

• Count Numbers with Unique Digits (LC 357) — intro digit DP
• Numbers At Most N Given Digit Set (LC 902)
• Non-negative Integers without Consecutive Ones (LC 600)

Hard / Advanced

• Maximum Profit in Job Scheduling (LC 1235) — DP + binary search
• Strange Printer II (LC 1591)
• Minimum Number of Taps to Open to Water a Garden (LC 1326)
• K Inverse Pairs Array (LC 629)
• Paint House III (LC 1473) — 3D DP

Additional LeetCode Coverage

• Largest Divisible Subset (LC 368)
• Combination Sum IV (LC 377)
• Ones and Zeroes (LC 474)
• Longest Palindromic Subsequence (LC 516)
• Delete Operation for Two Strings (LC 583)
• Maximum Length of Pair Chain (LC 646)
• Minimum ASCII Delete Sum for Two Strings (LC 712)
• Delete and Earn (LC 740)
• Min Cost Climbing Stairs (LC 746)
• Domino and Tromino Tiling (LC 790)
• Maximum Sum Circular Subarray (LC 918)
• Minimum Cost For Tickets (LC 983)
• Uncrossed Lines (LC 1035)
• Longest String Chain (LC 1048)
• Shortest Common Supersequence (LC 1092)
• N-th Tribonacci Number (LC 1137)
• Longest Arithmetic Subsequence of Given Difference (LC 1218)
• Minimum Insertion Steps to Make a String Palindrome (LC 1312)
• Longest Subarray of 1's After Deleting One Element (LC 1493)
• Minimum Cost to Cut a Stick (LC 1547)
• Solving Questions With Brainpower (LC 2140)
• Count Ways To Build Good Strings (LC 2466)
• Pascal's Triangle II (LC 119)
• Best Time to Buy and Sell Stock II (LC 122)
• Best Time to Buy and Sell Stock III (LC 123)
• Best Time to Buy and Sell Stock IV (LC 188)

Clarification Questions to Ask

• What are the value ranges? (Determines if knapsack is feasible; confirms need for modular arithmetic.)
• Can values be negative? (Affects Kadane's; changes knapsack formulation.)
• Are items distinguishable or identical? (Combinations vs. permutations in counting DP.)
• Is the answer count, min, max, or existence? (Determines initialization and transition operation.)
• Can we reuse elements? (0/1 vs. unbounded knapsack; combination vs. permutation.)
• What is the definition of "subsequence" — contiguous or not? ("Subarray" = contiguous; "subsequence" = not necessarily.)
• Is the sequence 0-indexed or 1-indexed in the output? (Affects reconstruction.)
• Integer overflow: should the answer be returned modulo 10^9+7?

Common Interview Mistakes

• Defining states with insufficient information, then patching with global variables — always make state self-contained.
• Confusing subarray (contiguous) with subsequence (not necessarily contiguous) and writing the wrong transition.
• Forgetting to handle the "do nothing" base case in knapsack (capacity 0 = value 0).
• Iterating in wrong direction for rolling-array knapsack (left-to-right for 0/1 knapsack gives unbounded behavior).
• Initializing counting DP with 0 everywhere instead of dp[0]=1 (empty prefix base case).
• Returning dp[n] when the answer is max(dp) — for subsequence problems, the answer may end at any index.
• Forgetting to subtract 1 in palindrome cuts (dp[i]-1 cuts for i characters, not dp[i] cuts).
• Using float('inf') as initial value but not handling the case where float('inf') + cost propagates incorrectly — always check reachability before using a value.

Typical Follow-Up Escalations

• "Now do it in O(1) space" → rolling array; identify which previous rows are needed.
• "Now reconstruct the actual solution, not just the value" → store choice array alongside dp; backtrack.
• "Now do it for k transactions / k groups" → add a dimension for k; verify if O(nk) is acceptable.
• "The values are too large for a table — n = 10^9" → check if states are sparse; switch to memoization with hashmap; look for mathematical closed form.
• "Can you do better than O(n²)?" → LIS: O(n log n) tails; knapsack: bitset trick O(nW/64); interval DP: Knuth's O(n²).
• "What if elements can be negative?" → re-examine initialization; Kadane's handles it natively; knapsack may need to allow negative capacity states.