--- # === IDENTITY === id: software/patterns/dynamic-programming/2026 canonical_question: "What are the core dynamic programming patterns and techniques?" aliases: - "dynamic programming patterns for coding interviews" - "DP memoization vs tabulation when to use" - "knapsack LCS LIS coin change DP solutions" - "bitmask DP digit DP tree DP interval DP guide" - "top-down vs bottom-up dynamic programming" - "how to identify and solve DP problems" entity_type: software_reference domain: software > patterns > dynamic_programming region: global jurisdiction: global temporal_scope: 1957-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "DP only applies when a problem has both overlapping subproblems AND optimal substructure; verify both properties before choosing DP" - "Bitmask DP is limited to n <= 20-25 elements due to 2^n state space; beyond that, use alternative approaches" - "Digit DP range limits (e.g., 10^18) mean individual iteration is impossible; the digit decomposition is mandatory, not optional" - "Memoized recursion (top-down) risks stack overflow for deep recursion (n > 10,000 in Python, ~100,000 in Java/C++); use tabulation for large inputs" - "Space-optimized DP (rolling array) destroys the ability to reconstruct the solution path; keep the full table if you need the actual sequence, not just the value" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Problem has greedy choice property and no overlapping subproblems" use_instead: "Use greedy algorithms (activity selection, Huffman coding, Kruskal/Prim)" - condition: "Problem requires exploring all valid configurations without optimization" use_instead: "Use backtracking with pruning (N-Queens, Sudoku, permutation generation)" - condition: "State space is a graph with unweighted edges" use_instead: "Use BFS/DFS for graph traversal; DP on DAGs only when topological order exists" # === AGENT HINTS === inputs_needed: - key: problem_type question: "What type of problem are you solving?" type: choice options: ["optimization (min/max)", "counting (number of ways)", "existence (is it possible?)", "construction (find the actual solution)"] - key: dp_pattern question: "Which DP pattern best matches your problem structure?" type: choice options: ["1D linear", "2D grid", "knapsack (0/1 or unbounded)", "LCS/LIS subsequence", "interval DP", "bitmask DP", "digit DP", "tree DP", "state machine DP", "not sure"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/dynamic-programming/2026" suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/graph-algorithms/2026" label: "Graph Algorithms Reference" - id: "software/patterns/sorting-algorithms/2026" label: "Sorting Algorithms Reference" - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" solves: [] alternative_to: - id: "software/patterns/backtracking-patterns/2026" label: "Backtracking Patterns (exhaustive search alternative)" often_confused_with: - id: "software/patterns/greedy-algorithms/2026" label: "Greedy Algorithms (no overlapping subproblems)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Introduction to Algorithms (CLRS) — Dynamic Programming Chapters 14-15" author: Cormen, Leiserson, Rivest, Stein url: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ type: academic_paper published: 2022-04-05 reliability: authoritative - id: src2 title: "Dynamic Programming Patterns — LeetCode Discussion" author: LeetCode Community url: https://leetcode.com/discuss/study-guide/1437879/dynamic-programming-patterns/ type: community_resource published: 2021-09-15 reliability: moderate_high - id: src3 title: "20 Patterns to Master Dynamic Programming" author: AlgoMaster url: https://blog.algomaster.io/p/20-patterns-to-master-dynamic-programming type: technical_blog published: 2024-06-10 reliability: moderate_high - id: src4 title: "Introduction to Dynamic Programming — CP-Algorithms" author: CP-Algorithms url: https://cp-algorithms.com/dynamic_programming/intro-to-dp.html type: community_resource published: 2024-01-15 reliability: high - id: src5 title: "Dynamic Programming (DP) Introduction — GeeksforGeeks" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/introduction-to-dynamic-programming-data-structures-and-algorithm-tutorials/ type: community_resource published: 2024-08-20 reliability: moderate_high - id: src6 title: "Tabulation vs Memoization — GeeksforGeeks" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/tabulation-vs-memoization/ type: community_resource published: 2024-03-12 reliability: moderate_high - id: src7 title: "Digit DP — USACO Guide" author: USACO Guide url: https://usaco.guide/gold/digit-dp type: community_resource published: 2024-05-01 reliability: high --- # Dynamic Programming Patterns: Complete Reference ## TL;DR - **Bottom line**: Identify overlapping subproblems + optimal substructure, then choose memoization (top-down) or tabulation (bottom-up) to eliminate redundant computation. - **Key tool**: `dp[state] = combine(dp[subproblems])` -- define the state, write the recurrence, fill the table. - **Watch out for**: Space optimization opportunities -- most 2D DP can be reduced to 1D with rolling arrays, cutting memory by O(n). - **Works with**: Any language; patterns are language-agnostic. Python, JavaScript/TypeScript, Java, C++, Go all apply identically. ## Constraints - DP only applies when a problem has both overlapping subproblems AND optimal substructure; verify both before choosing DP - Bitmask DP is limited to n <= 20-25 elements (2^n states); for larger sets, use approximation or alternative algorithms - Memoized recursion risks stack overflow for deep recursion (Python default limit: 1,000; Java ~10,000); use tabulation for large n - Space-optimized DP (rolling array) destroys solution reconstruction; keep full table when you need the actual path/sequence - Digit DP requires digit-by-digit decomposition; iterating through the entire range [L, R] is computationally infeasible for large bounds ## Quick Reference | DP Pattern | Time | Space | Classic Problems | Key Insight | |---|---|---|---|---| | 1D Linear | O(n) or O(n*k) | O(n) or O(1) | Fibonacci, Climbing Stairs, House Robber | Each state depends on a fixed number of previous states | | 2D Grid | O(m*n) | O(m*n) or O(n) | Unique Paths, Minimum Path Sum, Dungeon Game | State = (row, col); transitions from adjacent cells | | 0/1 Knapsack | O(n*W) | O(n*W) or O(W) | Subset Sum, Partition Equal Subset, Target Sum | Each item used at most once; iterate items then capacity | | Unbounded Knapsack | O(n*W) | O(W) | Coin Change, Rod Cutting, Integer Break | Items reusable; iterate capacity then items (or same direction) | | LCS (Longest Common Subsequence) | O(m*n) | O(m*n) or O(n) | Edit Distance, Shortest Common Supersequence | dp[i][j] = match/mismatch on s1[i] vs s2[j] | | LIS (Longest Increasing Subsequence) | O(n log n) | O(n) | Patience Sorting, Russian Doll Envelopes | Binary search on tails array for O(n log n) | | Interval DP | O(n^3) | O(n^2) | Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning | Merge smaller intervals; enumerate split point k | | Bitmask DP | O(2^n * n) | O(2^n) | TSP, Assignment Problem, Hamiltonian Path | Bitmask encodes subset; n <= 20 | | Digit DP | O(d * tight * state) | O(d * tight * state) | Count numbers with digit sum = k, Numbers without consecutive 1s | Process digits left to right with tight constraint | | Tree DP | O(n) | O(n) | Diameter, Max Path Sum, Independent Set on Tree | Post-order traversal; merge child subtree results | | State Machine DP | O(n * states) | O(states) | Best Time to Buy/Sell Stock (all variants), String editing with modes | Finite states with explicit transitions per step | | Profile DP (Broken Profile) | O(n * 2^m) | O(2^m) | Domino/Tromino Tiling, Grid coloring with constraints | Encode column boundary as bitmask; m <= 20 | [src1] [src2] [src3] ## Decision Tree ``` START: Does the problem have overlapping subproblems? |-- NO --> Not a DP problem. Try greedy, divide & conquer, or brute force. |-- YES --> Does it have optimal substructure? |-- NO --> DP won't yield optimal solution. Try brute force with pruning. |-- YES --> Choose DP approach: |-- Can you define states easily from the end? | |-- YES --> Use bottom-up tabulation (iterative, no stack risk) | |-- NO --> Use top-down memoization (recursive, natural for trees/DAGs) | |-- Identify the pattern: |-- Single sequence/array? --> 1D Linear DP or LIS |-- Two sequences to compare? --> LCS / Edit Distance (2D) |-- Grid traversal? --> 2D Grid DP |-- Items with weight/value, capacity limit? | |-- Each item once? --> 0/1 Knapsack | |-- Items reusable? --> Unbounded Knapsack |-- Merging ranges or splitting? --> Interval DP |-- Small set (n <= 20) with subset tracking? --> Bitmask DP |-- Count integers in [L, R] with digit property? --> Digit DP |-- Tree structure? --> Tree DP (post-order DFS) |-- Multiple modes/states per step? --> State Machine DP |-- None of the above? --> Define custom state; check for DAG structure ``` [src2] [src3] ## Step-by-Step Guide ### 1. Identify DP applicability Verify the problem has both properties: (a) overlapping subproblems -- solving it recursively would recompute the same subproblem multiple times, and (b) optimal substructure -- the optimal solution to the problem contains optimal solutions to its subproblems. [src1] **Verify**: Draw the recursion tree for a small input. If you see repeated nodes, DP applies. ### 2. Define the state The state is the minimum set of variables that uniquely describes a subproblem. Common states: `dp[i]` (position in array), `dp[i][j]` (two pointers or grid position), `dp[i][w]` (item index + remaining capacity), `dp[mask]` (subset bitmask). [src1] **Verify**: Can you express the answer to the original problem in terms of your state? e.g., answer = `dp[n]` or `dp[n][W]`. ### 3. Write the recurrence relation Express `dp[state]` in terms of smaller subproblems. This is the core mathematical insight. Example for 0/1 Knapsack: `dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])`. [src1] **Verify**: Manually trace the recurrence on a 3-4 element input to confirm correctness. ### 4. Determine the base cases Identify the smallest subproblems that can be solved directly. Examples: `dp[0] = 0` (no items), `dp[0][0] = 1` (empty subset sums to 0), `dp[leaf] = leaf.val` (tree leaf). [src5] **Verify**: Base cases should prevent out-of-bounds access and produce correct answers for trivial inputs. ### 5. Choose implementation approach **Top-down (memoization)**: Write the recursive solution, add a cache (hash map or array). Natural for tree DP and problems where not all states are visited. **Bottom-up (tabulation)**: Fill the DP table iteratively in topological order. Better for space optimization and avoiding stack overflow. [src6] **Verify**: Both approaches should produce identical results on test cases. ### 6. Optimize space if possible Check if `dp[i]` only depends on `dp[i-1]` (or a fixed window). If so, reduce from O(n*m) to O(m) with a rolling array. For 1D DP depending on `dp[i-1]` and `dp[i-2]`, reduce to O(1) with two variables. [src4] **Verify**: Run optimized version against full-table version on test cases; results must match. ## Code Examples ### Python: 0/1 Knapsack (Bottom-Up with Space Optimization) ```python # Input: weights = [2, 3, 4, 5], values = [3, 4, 5, 6], capacity = 8 # Output: Maximum value achievable = 10 def knapsack_01(weights, values, capacity): n = len(weights) # Space-optimized: single row, iterate capacity in reverse dp = [0] * (capacity + 1) for i in range(n): # Reverse order prevents using same item twice for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity] ``` ### Python: Longest Common Subsequence ```python # Input: s1 = "abcde", s2 = "ace" # Output: Length of LCS = 3 ("ace") def lcs(s1, s2): m, n = len(s1), len(s2) # Space-optimized: two rows prev = [0] * (n + 1) curr = [0] * (n + 1) for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]: curr[j] = prev[j-1] + 1 else: curr[j] = max(prev[j], curr[j-1]) prev, curr = curr, [0] * (n + 1) return prev[n] ``` ### Python: Coin Change (Unbounded Knapsack) ```python # Input: coins = [1, 5, 10, 25], amount = 30 # Output: Minimum coins needed = 2 (5 + 25) def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 # base case: 0 coins for amount 0 for coin in coins: for a in range(coin, amount + 1): dp[a] = min(dp[a], dp[a - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 ``` ### JavaScript: Edit Distance (Levenshtein) ```javascript // Input: word1 = "horse", word2 = "ros" // Output: Minimum operations = 3 function editDistance(word1, word2) { const m = word1.length, n = word2.length; // dp[j] = edit distance between word1[0..i] and word2[0..j] let prev = Array.from({length: n + 1}, (_, j) => j); for (let i = 1; i <= m; i++) { const curr = [i]; // base: delete all of word1[0..i] for (let j = 1; j <= n; j++) { if (word1[i-1] === word2[j-1]) { curr[j] = prev[j-1]; // chars match, no operation } else { curr[j] = 1 + Math.min(prev[j-1], prev[j], curr[j-1]); // replace, delete, insert respectively } } prev = curr; } return prev[n]; } ``` ### Python: Fibonacci with Memoization vs Tabulation ```python # Top-down (memoization) from functools import lru_cache @lru_cache(maxsize=None) def fib_memo(n): if n <= 1: return n return fib_memo(n - 1) + fib_memo(n - 2) # Bottom-up (tabulation, O(1) space) def fib_tab(n): if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b ``` ## Anti-Patterns ### Wrong: Recursion without memoization ```python # BAD -- exponential O(2^n) time, recomputes same subproblems def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) # fib(3) computed billions of times for large n ``` ### Correct: Add memoization or use tabulation ```python # GOOD -- O(n) time with memoization from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) ``` ### Wrong: Wrong iteration direction in 0/1 Knapsack ```python # BAD -- forward iteration allows using same item multiple times dp = [0] * (capacity + 1) for i in range(n): for w in range(weights[i], capacity + 1): # WRONG: forward dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) ``` ### Correct: Reverse iteration for 0/1 Knapsack ```python # GOOD -- reverse iteration ensures each item used at most once dp = [0] * (capacity + 1) for i in range(n): for w in range(capacity, weights[i] - 1, -1): # RIGHT: reverse dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) ``` ### Wrong: Using wrong base case for counting problems ```python # BAD -- dp[0] = 0 means "zero ways to make amount 0" dp = [0] * (amount + 1) dp[0] = 0 # WRONG for counting: there IS one way to make 0 (use no coins) for coin in coins: for a in range(coin, amount + 1): dp[a] += dp[a - coin] # Result: always 0 ``` ### Correct: Base case dp[0] = 1 for counting problems ```python # GOOD -- exactly one way to make amount 0: choose nothing dp = [0] * (amount + 1) dp[0] = 1 # one way to make 0 for coin in coins: for a in range(coin, amount + 1): dp[a] += dp[a - coin] ``` ### Wrong: Interval DP with wrong loop order ```python # BAD -- accessing dp[i][k] and dp[k+1][j] before they are computed for i in range(n): for j in range(i, n): for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost) ``` ### Correct: Interval DP iterating by length ```python # GOOD -- iterate by interval length so smaller intervals are computed first for length in range(2, n + 1): # interval length for i in range(n - length + 1): # start index j = i + length - 1 # end index for k in range(i, j): # split point dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost) ``` ## Common Pitfalls - **Off-by-one in state definition**: DP tables are often 1-indexed (`dp[0]` = base case) but input arrays are 0-indexed. Mixing indices is the #1 source of bugs. Fix: explicitly document whether `dp[i]` means "first i items" or "item at index i". [src5] - **Forgetting to initialize dp table**: Uninitialized values (0 or garbage) can silently produce wrong answers. For minimization problems, initialize with `float('inf')` or `INT_MAX`, not 0. Fix: `dp = [float('inf')] * (n+1); dp[0] = 0`. [src4] - **Confusing 0/1 vs unbounded knapsack iteration order**: Forward iteration on capacity = unbounded (items reusable); reverse = 0/1 (items used once). Swapping them changes the problem entirely. Fix: always comment which variant you're implementing. [src2] - **Stack overflow with deep memoization**: Python's default recursion limit is 1,000. For n = 10,000, top-down DP will crash. Fix: `sys.setrecursionlimit(n + 100)` or convert to bottom-up tabulation. [src6] - **Not handling impossible states**: Returning `dp[target]` without checking if it was ever updated. For coin change, `dp[amount]` might still be `inf` (no valid combination exists). Fix: always check `dp[answer] != sentinel` before returning. [src5] - **Reconstructing solution from space-optimized table**: After rolling-array optimization, previous rows are overwritten. You cannot trace back the path. Fix: if you need the actual solution (not just the value), keep the full 2D table or store choice arrays separately. [src1] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Problem has overlapping subproblems AND optimal substructure | Problem has greedy choice property (locally optimal = globally optimal) | Greedy algorithms (Dijkstra, Huffman, interval scheduling) | | Need optimal value (min/max) or count of solutions | Need to enumerate ALL valid configurations | Backtracking with pruning | | State space is polynomial (n, n*W, n^2, n^3) | State space is exponential and n > 25 | Branch and bound, approximation algorithms | | Subproblems form a DAG (no cycles in dependency) | Subproblems have circular dependencies | Iterative deepening, fixed-point computation | | Problem can be decomposed into independent subproblems | Subproblems are interdependent (changing one affects others) | Simulation, constraint programming | ## Important Caveats - Time complexity of DP is number_of_states * transition_cost_per_state. A "polynomial" DP can still be too slow if the state space constant is large (e.g., O(n^3) with n=5,000 is 125 billion operations). - DP on trees requires post-order (bottom-up) DFS; DP on DAGs requires topological sort. Applying DP to a general graph with cycles will loop infinitely or produce wrong answers. - Python's `@lru_cache` stores results in a dictionary, which has higher constant overhead than array-based tabulation. For performance-critical code (competitive programming), prefer tabulation with pre-allocated arrays. - Integer overflow is a concern in counting problems. In C++/Java, use `long long` / `long` or modular arithmetic (`% 10^9 + 7`). Python handles big integers natively but at the cost of speed. - Floating-point DP (e.g., probability problems) accumulates rounding errors. Use log-space DP or exact rational arithmetic when precision matters. ## Related Units - [Graph Algorithms Reference](/software/patterns/graph-algorithms/2026) - [Sorting Algorithms Reference](/software/patterns/sorting-algorithms/2026) - [Binary Search Variations](/software/patterns/binary-search-variations/2026) - [Backtracking Patterns](/software/patterns/backtracking-patterns/2026) - [Greedy Algorithms](/software/patterns/greedy-algorithms/2026)