On this page

Dynamic Programming

Dynamic programming (DP) is the algorithm design technique that strikes fear into interviewees. It shouldn't. DP is simply recursion without redundancy — you solve each subproblem once, store the result, and reuse it. The hard part is seeing that a problem has the right structure for DP. Once you can identify the state, the transition, and the base case, the code writes itself.

This page is the overview lesson of Module 6 — Dynamic Programming in DSA: Zero to Mastery, and it is also the module's landing page. The first part (down to "When to Use DP") is the map: what the twenty lessons and the capstone cover, why they come in this order, and a table that tells you which DP family a problem belongs to from the words in its statement. The second part is a fast tour of the classic problems — Fibonacci, climbing stairs, coin change, LIS, house robber, LCS, edit distance, knapsack, matrix chain, word break — each with its state, recurrence and code, and a pointer to the lesson that goes deeper.

Previous module: Module 5 · Paradigms (recursion and backtracking, divide and conquer, greedy, bit manipulation, randomized algorithms). Next: Module 7 · String Algorithms.

How this module is organised

Module 6 has one overview (this page), twenty lessons and a capstone. It starts with the one framework every DP uses, then works through the families of DP grouped by the shape of the state — a position in a line, a pair of positions, a range, a tree node, a set, a digit position — then the families grouped by what is computed (counts, probabilities, game values), and ends with how to make a DP fast and how to debug one.

#LessonWhat you will be able to doMinutes
1Dynamic Programming (Overview)Recognise a DP problem, name its family, and recall the state and recurrence of the ten classic problems.45
2DP FoundationsDerive any DP with five questions (state, transition, base, answer, order), choose memoization or tabulation, reconstruct the answer and roll arrays.60
31-D DPSolve linear problems (stairs, robbers, decoding, maximum subarray, stock trading) with dp[i] and small state machines.50
4KnapsackSolve 0/1, unbounded, bounded and multi-dimensional knapsack, subset sum and coin change, and explain pseudo-polynomial time.55
5Sequence DPCompute LIS in , LCS, edit distance and alignments, and reconstruct them (including in linear space).60
6String DPFill prefix-by-prefix tables for word break, wildcard and regex matching, distinct subsequences, palindrome partitioning and interleaving.60
7Grid & Path DPCount and optimise paths on grids, fill backwards when the state is simpler at the goal, and synchronise two walkers.55
8Interval DPSolve range problems (matrix chain, burst balloons, optimal BST, palindromes) by choosing the last operation in a range.55
9Partition DPCut a sequence into contiguous groups optimally (painters, splitting arrays, text justification).45
10Tree DPCompute per-subtree states in post-order, and answer "for every root" questions with rerooting.55
11DAG DPSee every DP as a path problem on a DAG; longest paths, path counts and memoised DFS on implicit DAGs.45
12Bitmask DPUse a subset as the state for : travelling salesman, assignment, Hamiltonian paths.55
13SOS DPSum (or OR, max) over all submasks of every mask in instead of .45
14Digit DPCount integers in with a digit property using the (position, tight, property) state.50
15Broken-Profile DPTile narrow grids with dominoes and shapes by carrying a bitmask profile across cells.50
16Counting DPCount arrangements modulo a prime without double counting, and combine DP with combinatorics.55
17Probability DPCompute probabilities and expected values over random processes, including states that loop.50
18Game DPSolve two-player optimal-play games with win/lose states and score differences; connect to Sprague-Grundy.50
19Matrix ExponentiationTurn a fixed-size linear recurrence into a matrix power and evaluate it for up to .45
20DP OptimizationsSpeed up transitions with monotonic queues, convex hull trick, divide-and-conquer DP, Knuth and Aliens tricks.75
21DP Debugging & How to Find the StateFind a state with a checklist and a dimension audit, recognise the common DP bugs, and stress-test a DP against brute force.50
—Capstone: A Diff Tool and a Spell-Checker with DPBuild an LCS line diff with unified output, edit-distance spelling suggestions, minimum-raggedness line breaking, and benchmark the full table against two rows.180–240

The whole module is about 18 hours of reading and tracing plus the capstone; the practice ladders roughly double it. It is the longest module in the course because DP is less a single algorithm than a way of thinking, and the only way to learn it is many problems.

Module 6 at a glance

Dynamic programming solves a problem by solving smaller instances of the same problem, storing each answer, and combining stored answers — so that every distinct subproblem is solved exactly once. It applies when the subproblems overlap (the same smaller question comes up many times) and when the best answer is built from best answers to subproblems (optimal substructure). Every DP is specified by the same five things: the state (what a subproblem is), the transition (how to compute a state from smaller ones), the base cases, the answer state, and an order in which to compute the states. Learning DP is mostly learning to find the state; everything else follows from it.

What this module covers

Twenty lessons after this overview, in six arcs, and a capstone.

Arc 1 — the framework. DP Foundations gives the five questions, memoization versus tabulation (with the recursion-depth limits of each language), reconstruction, rolling arrays, and ten classic problems derived the same way. 1-D DP is the simplest state shape, a position in a line, including small per-position state machines. Knapsack adds a resource budget as a second dimension and introduces pseudo-polynomial time.

Arc 2 — two indices. Sequence DP (LIS, LCS, edit distance, alignment), String DP (matching and segmenting strings) and Grid & Path DP (paths on boards) all fill a two-dimensional table where each cell reads its neighbours. They are the same idea seen from three angles: two prefixes, a prefix of text and a prefix of pattern, a row and a column.

Arc 3 — structure-shaped states. Interval DP uses a range as the state and splits on the last operation; Partition DP cuts a line into groups; Tree DP uses a subtree; DAG DP makes explicit that every DP is a path computation on the DAG of its subproblems, linking back to Topological Sort.

Arc 4 — compressed states. When the past must be remembered as a set, Bitmask DP stores it in an integer (), and SOS DP aggregates over all subsets fast. Digit DP walks the digits of a number with a "tight" flag; Broken-Profile DP walks a grid cell by cell with a bitmask frontier.

Arc 5 — what you compute. Counting DP (counts modulo a prime, avoiding double counting), Probability DP (expected values), Game DP (optimal play) and Matrix Exponentiation (linear recurrences for astronomically large ).

Arc 6 — fast and correct. DP Optimizations keeps the state and speeds up the transition (monotonic deque, convex hull trick, divide and conquer, Knuth). DP Debugging & How to Find the State is the toolkit for when you are stuck: a state-finding checklist, a dimension audit, a bug catalogue, and a stress-test harness in four languages.

Capstone. A Diff Tool and a Spell-Checker with DP: an LCS-based line diff with unified output, edit-distance spelling suggestions with a BK-tree, minimum-raggedness line breaking (partition DP), and a benchmark of the full table against the two-row version — deriving each state, verifying it against a brute force with the harness from the debugging lesson, and measuring what each optimisation buys.

Why in this order

Foundations first, because the framework is the subject. Every later lesson is "the five questions, with a new kind of state". If the framework is solid, a new family is one new idea; if not, every family feels like a list of tricks to memorise.

1-D, then knapsack, then two indices. Each step adds exactly one dimension. 1-D DP teaches the "last decision" transition with a one-number state. Knapsack adds a budget dimension and the first loop-direction subtlety (0/1 versus unbounded). Sequence, string and grid DPs then add a second position, and with it the 2-D table you can draw and trace by hand. Sequence DP comes before String DP because string matching (wildcards, regex) is LCS-style alignment with richer transitions; Grid DP closes the arc because it is the same table with the strings removed, and its "fill backwards" idea is needed next.

Intervals before partitions before trees before DAGs. Interval DP introduces splitting a range at an interior point, which partition DP specialises (split a prefix into groups) and tree DP generalises (split at a node's children). DAG DP comes last in the arc because it is the unifying view: once you have seen four state shapes, "they are all paths in a subproblem DAG" is an insight rather than an abstraction.

Compressed states after structural ones. Bitmask DP needs comfort with bit manipulation and with states that are not positions. SOS DP is an optimisation of bitmask aggregation, so it follows directly. Digit DP and broken-profile DP both carry a small "frontier" (tight flag, profile mask) along a walk, which is easiest to accept after bitmasks.

What-you-compute last among the families. Counting, probability and game DPs reuse every state shape above; they change the values (sums modulo , expectations, win/lose) rather than the states. Matrix exponentiation follows counting because it is a counting DP with a fixed-size state run for steps.

Optimisations and debugging at the end — but read debugging early. Optimisations only make sense once you have correct DPs that are too slow. The debugging lesson is placed last because its examples come from every family, but it is written to be read right after DP Foundations and revisited whenever you are stuck.

flowchart TD
    M5["Module 5 · Paradigms"] --> OV["DP overview"]
    OV --> FND["DP Foundations"]
    FND --> ONE["1-D DP"]
    FND --> DBG["DP Debugging"]
    ONE --> KS["Knapsack"]
    ONE --> SEQ["Sequence DP"]
    SEQ --> STR["String DP"]
    SEQ --> GRID["Grid DP"]
    SEQ --> INT["Interval DP"]
    INT --> PART["Partition DP"]
    INT --> TREE["Tree DP"]
    GRID --> DAG["DAG DP"]
    TREE --> DAG
    KS --> BM["Bitmask DP"]
    BM --> SOS["SOS DP"]
    ONE --> DIG["Digit DP"]
    BM --> BP["Broken-Profile DP"]
    KS --> CNT["Counting DP"]
    CNT --> PROB["Probability DP"]
    DAG --> GAME["Game DP"]
    CNT --> MAT["Matrix Exponentiation"]
    PART --> OPT["DP Optimizations"]
    KS --> OPT
    OPT --> CAP["Capstone"]
    DBG --> CAP
    STR --> CAP
    CAP --> M7["Module 7 · String Algorithms"]

Arrows mean "read this first". DP Debugging hangs off Foundations on purpose: read it early. Digit DP needs only 1-D thinking plus the "tight" idea; Game DP is easiest after DAG DP because a game's positions form a DAG (or, with cycles, need the retrograde analysis covered there).

Which DP family?

The literal words in a problem statement are the fastest guide to the state. Match the first row that fits; if none does, run the checklist in DP Debugging.

If the problem says or has…FamilyTypical stateLesson
"number of ways to climb / reach / decode", decisions along a line looking back a fixed distance1-D DPdp[i]1-D DP
"cannot pick adjacent", "cooldown", "at most transactions"1-D DP with a small state machinedp[i][state]1-D DP
Items with weight and value, a capacity, a target sum, "each at most once" / "unlimited"Knapsackdp[i][c] or dp[c]Knapsack
"subsequence", "longest common", "edit / insert / delete / replace", "align"Sequence DPdp[i][j] over prefixesSequence DP
"matches pattern with * and ?/.", "segment into words", "interleave", "palindrome partition"String DPprefix of text × prefix of patternString DP
A grid, "only right or down", "minimum path sum", "number of paths with obstacles"Grid DPdp[r][c]Grid & Path DP
"merge adjacent piles", "burst", "parenthesise", "cost depends on both neighbours", "remove from either end"Interval DPdp[l][r]Interval DP
"split the array into contiguous parts", "minimise the largest part", "line breaks"Partition DPdp[k][i]Partition DP
A tree, "no parent and child both chosen", "subtree", "for every node as root"Tree DPdp[v][flag], rerootingTree DP
"longest path in a DAG", "number of paths", dependencies, "strictly increasing moves in a matrix"DAG DPdp[v] in topological orderDAG DP
, "visit every city", "assign each person a task", "each used once"Bitmask DPdp[mask] or dp[mask][last]Bitmask DP
"for every mask, sum over its submasks / supersets", AND/OR pair countingSOS DPf[mask]SOS DP
"how many integers in " with a digit condition, up to Digit DP(pos, tight, …)Digit DP
Tile an board with dominoes or trominoes, one side or soBroken-profile DP(cell, profile)Broken-Profile DP
"count … modulo ", permutations or arrangements with constraintsCounting DPcounts with %Counting DP
"expected number of steps", "probability that", dice, random walksProbability DPE[state], P[state]Probability DP
"two players", "both play optimally", "who wins", "maximise your score minus theirs"Game DPwin[state], score differenceGame DP
A linear recurrence and up to ; "number of walks of length "Matrix exponentiationtransition matrixMatrix Exponentiation
Correct or DP, limits demand faster; transition is a min over a window or a lineDP optimisationsame state, faster transitionDP Optimizations
Moves in all directions, cycles, non-negative weightsNot DP — shortest pathdist[v]Shortest Paths
"list all solutions"Not DP — backtracking (DP can only count them)—Backtracking & Recursion
A provably safe local choice (exchange argument works)Not DP — greedy—Greedy Algorithms

Prerequisites

From Module 0: Recursion & Mathematical Induction — every DP starts as a recursion and every DP proof is an induction over the order of computation — and Complexity Analysis, because you will estimate states × transitions before writing code. Testing & Debugging Algorithms supplies the brute-force comparator habit that the debugging lesson builds on. From Module 1: Prefix Sums and the monotonic deque, both reused to speed up transitions. From Module 4: Topological Sort, the formal version of "an order in which to compute the states". From Module 5: Backtracking & Recursion (DP is backtracking that remembers), Greedy Algorithms (and when greedy fails, which is often how you know you need DP) and Bit Manipulation for the bitmask lessons.

You need one of Python 3.12+, Java 21, C++17 or later, or TypeScript (Node 22+). Every canonical implementation in the module is given in all four and checks itself.

How to study this module

Write the state sentence before any code. "dp[i][c] = the best value using the first i items with capacity at most c." If you cannot write it in one sentence, you are not ready to code — run the state-finding checklist.

Brute force first, then memoize, then tabulate. The brute-force recursion shows you the state (its parameters), and it is the oracle you will stress-test against. This is slower for the first few problems and much faster from then on.

Trace a small table by hand. Every lesson has a trace table computed by a script. Cover it, fill the table yourself for the small input, then compare. The first cell where you disagree is a misunderstanding caught before it became a bug.

Learn families, not problems. After each problem, write one line: "family, state, transition". The Which DP family? table above is the index those lines go into. Interviews reuse families far more than problems.

Two passes through the practice ladders. The first half of each ladder as you read; the hard tail after you have finished the arc. DP skill grows with the number of states you have designed, not with the number of solutions you have read.

Start with DP Foundations, then follow the table. Previous module: Module 5 · Paradigms. Next module: String Algorithms. Course map: DSA: Zero to Mastery.

A fast tour of the classic problems

The rest of this page is the original quick tour: the two DP properties, memoization versus tabulation, the four-question framework, and the classic 1-D, 2-D and interval problems with code. Each section points to the lesson that treats it in depth: DP Foundations for the framework, 1-D DP for stairs and robbers, Knapsack for coin change and knapsack, Sequence DP for LIS, LCS and edit distance, Interval DP for matrix chain, and String DP for word break.

When to Use DP

A problem is a DP candidate when it has two properties:

  1. Optimal substructure: The optimal solution contains optimal solutions to subproblems
  2. Overlapping subproblems: The same subproblems are solved multiple times
graph TD
    F5["fib(5)"] --> F4["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4 --> F3b["fib(3)"]
    F4 --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    style F3a fill:#f96
    style F3b fill:#f96
    style F2a fill:#ff0
    style F2b fill:#ff0
    style F2c fill:#ff0

Fibonacci without memoization: fib(3) is computed twice, fib(2) three times. This exponential redundancy is what DP eliminates.

Top-Down (Memoization) vs Bottom-Up (Tabulation)

Top-Down: Memoization

Start from the main problem, recurse into subproblems, cache results.

TypeScript:

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n)!;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

Python:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Bottom-Up: Tabulation

Start from the smallest subproblems, build up to the answer iteratively.

TypeScript:

function fibTab(n: number): number {
  if (n <= 1) return n;

  const dp = new Array(n + 1);
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

// Space-optimized: O(1) instead of O(n)
function fibOptimized(n: number): number {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;

  for (let i = 2; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Python:

def fib_tab(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fib_optimized(n: int) -> int:
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Comparison

Top-Down (Memoization)Bottom-Up (Tabulation)
ApproachRecursive + cacheIterative + table
Solves all subproblems?Only what's neededAll subproblems
Stack overflow riskYes (deep recursion)No
Space optimizationHarderEasier (rolling array)
Thinking styleNatural (start from goal)Requires ordering subproblems

TIP

Start with top-down memoization when solving a new problem — it maps directly to the recursive structure and is easier to reason about. Convert to bottom-up for production code where stack overflow is a concern or space optimization is needed.

The DP Framework

For any DP problem, answer these four questions:

  1. State: What information defines a subproblem? → This becomes your DP array dimensions
  2. Transition: How does a state relate to smaller states? → This is your recurrence relation
  3. Base case: What are the trivial subproblems? → Initialization of your DP array
  4. Answer: Which state contains the final answer?

A fifth question: order

DP Foundations adds Order — in which sequence to compute the states so that every state's inputs are ready — and applies all five questions to ten classic problems with trace tables and code in four languages. When the state will not come, use the checklist in DP Debugging & How to Find the State.

1D Dynamic Programming

Climbing Stairs

Problem: You can climb 1 or 2 steps at a time. How many ways to reach the top of stairs?

State: dp[i] = number of ways to reach step

Transition: (come from one step or two steps below)

TypeScript:

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;

  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

Python:

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Complexity: time, space.

Coin Change

Problem: Given coin denominations and a target amount, find the minimum number of coins needed.

State: dp[amount] = minimum coins to make amount

Transition: for each coin

TypeScript:

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a && dp[a - coin] + 1 < dp[a]) {
        dp[a] = dp[a - coin] + 1;
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

Python:

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

Complexity: time, space.

Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest strictly increasing subsequence.

DP approach:

State: dp[i] = length of LIS ending at index

Transition:

approach with patience sorting:

Python:

import bisect

def length_of_lis(nums: list[int]) -> int:
    # tails[i] = smallest tail element for increasing subsequence of length i+1
    tails: list[int] = []

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

    return len(tails)

TypeScript:

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
    if (lo === tails.length) tails.push(num);
    else tails[lo] = num;
  }

  return tails.length;
}

Complexity: time, space.

House Robber

Problem: Rob houses along a street; cannot rob two adjacent houses. Maximize total loot.

Python:

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1

2D Dynamic Programming

Longest Common Subsequence (LCS)

Problem: Find the length of the longest common subsequence between two strings.

State: dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]

Transition:

TypeScript:

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length;
  const n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

Python:

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

Complexity: time, space (optimizable to with rolling array).

Edit Distance (Levenshtein Distance)

Problem: Minimum operations (insert, delete, replace) to transform one string into another.

State: dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]

Transition:

TypeScript:

function minDistance(word1: string, word2: string): number {
  const m = word1.length;
  const n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  // Base cases
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }

  return dp[m][n];
}

Python:

def min_distance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]

Complexity: time, space.

Production Use Case

Edit distance is used in spell checkers, DNA sequence alignment, diff tools, and fuzzy search. It's not just an interview problem — it's a foundational algorithm in bioinformatics and text processing.

0/1 Knapsack

Problem: Given items with weights and values and a capacity, maximize total value without exceeding the weight limit. Each item can be used at most once.

State: dp[i][w] = max value using first items with capacity

Transition:

Python:

def knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # don't take item i
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

# Space-optimized: single row, iterate capacity in reverse
def knapsack_optimized(weights: list[int], values: list[int], capacity: int) -> int:
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # reverse to avoid reuse
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

Complexity: time and space ( space optimized), where is the capacity. This is pseudo-polynomial — polynomial in the value of , not the number of bits needed to represent it.

Interval DP

Problems where the state is defined over a contiguous range.

Matrix Chain Multiplication

Problem: Find the most efficient way to multiply a chain of matrices.

Python:

def matrix_chain_order(dims: list[int]) -> int:
    """dims[i-1] x dims[i] is the dimension of matrix i."""
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]

    # l is the chain length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n - 1]

Complexity: time, space.

State Transition Thinking Framework

When you encounter a new DP problem, follow this systematic process:

graph TD
    A["1. Identify the choices<br/><small>What decisions do you make at each step?</small>"] --> B["2. Define the state<br/><small>What information captures a subproblem?</small>"]
    B --> C["3. Write the recurrence<br/><small>How does current state relate to smaller states?</small>"]
    C --> D["4. Identify base cases<br/><small>What are the trivial subproblems?</small>"]
    D --> E["5. Determine computation order<br/><small>Which subproblems must be solved first?</small>"]
    E --> F["6. Extract the answer<br/><small>Which state contains the final result?</small>"]

Example Walkthrough: Word Break

Problem: Given a string and a dictionary, determine if the string can be segmented into dictionary words.

  1. Choices: At each position, try every possible word from the dictionary that starts there
  2. State: dp[i] = can s[0..i-1] be segmented?
  3. Recurrence: dp[i] = any(dp[j] and s[j:i] in wordDict for j in range(i))
  4. Base case: dp[0] = True (empty string)
  5. Order: Left to right
  6. Answer: dp[len(s)]

Python:

def word_break(s: str, word_dict: list[str]) -> bool:
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break

    return dp[len(s)]

Common DP Patterns

PatternExamplesState Hint
Linear sequenceClimbing stairs, house robber, LISdp[i] indexed by position
Two sequencesLCS, edit distancedp[i][j] two indices
Knapsack / subset0/1 knapsack, subset sum, coin changedp[i][capacity] or dp[capacity]
IntervalMatrix chain, burst balloons, palindrome partitiondp[i][j] for range
GridUnique paths, min path sumdp[row][col]
BitmaskTraveling salesman, set coverdp[mask] where mask is a bitmask
String partitionWord break, palindrome partitioningdp[i] or dp[i][j]

Common Mistakes

  • Not handling base cases correctly: Off-by-one errors in DP indices are the #1 source of bugs
  • Wrong computation order: In bottom-up, you must fill states that are dependencies first
  • Forgetting to consider all transitions: Missing a case in the recurrence relation leads to wrong answers
  • Confusing 0/1 knapsack with unbounded: In 0/1 knapsack, iterate capacity in reverse; in unbounded, iterate forward

Space Optimization

Many 2D DP problems only depend on the previous row, allowing space instead of :

Before (LCS with space):

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

After (LCS with space):

prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if text1[i-1] == text2[j-1]:
            curr[j] = prev[j-1] + 1
        else:
            curr[j] = max(prev[j], curr[j-1])
    prev, curr = curr, [0] * (n + 1)

Practice Problems

ProblemPatternDifficulty
Climbing Stairs1D linearEasy
House Robber1D linearMedium
Coin Change1D knapsackMedium
Longest Increasing Subsequence1D + binary searchMedium
Word Break1D string partitionMedium
Longest Common Subsequence2D two-sequenceMedium
Edit Distance2D two-sequenceMedium
0/1 Knapsack2D subsetMedium
Unique Paths2D gridMedium
Longest Palindromic Substring2D intervalMedium
Burst BalloonsInterval DPHard
Regular Expression Matching2D two-sequenceHard

Further Reading

Try It Yourself

Problem 1: How many distinct ways can you climb a staircase of 5 steps, taking 1 or 2 steps at a time?

Solution

Use the climbing stairs recurrence: .

  • dp[1] = 1, dp[2] = 2
  • dp[3] = dp[2] + dp[1] = 3
  • dp[4] = dp[3] + dp[2] = 5
  • dp[5] = dp[4] + dp[3] = 8

Problem 2: Given coins [1, 3, 4] and amount 6, find the minimum number of coins needed.

Solution

Build the DP table: .

  • dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=1, dp[4]=1
  • dp[5] = min(dp[4]+1, dp[2]+1, dp[1]+1) = min(2, 3, 2) = 2
  • dp[6] = min(dp[5]+1, dp[3]+1, dp[2]+1) = min(3, 2, 3) = 2 Answer: 2 coins (3 + 3)

Problem 3: Find the Longest Common Subsequence of "ABCDE" and "ACE".

Solution

Build the 2D DP table where = LCS of first chars of s1 and first chars of s2:

  • A matches A → dp[1][1] = 1
  • C matches C → dp[3][2] = 2
  • E matches E → dp[5][3] = 3 Answer: 3 (the LCS is "ACE")

Problem 4: Given the array [10, 9, 2, 5, 3, 7, 101, 18], find the length of the Longest Increasing Subsequence.

Solution

Using the patience sorting / binary search approach, maintain tails:

  • 10 → tails=[10]
  • 9 → replace 10 → tails=[9]
  • 2 → replace 9 → tails=[2]
  • 5 → append → tails=[2,5]
  • 3 → replace 5 → tails=[2,3]
  • 7 → append → tails=[2,3,7]
  • 101 → append → tails=[2,3,7,101]
  • 18 → replace 101 → tails=[2,3,7,18] Answer: 4 (e.g., [2, 3, 7, 101] or [2, 3, 7, 18])

Problem 5: Compute the edit distance between "kitten" and "sitting".

Solution

Build the DP table:

  • k→s (replace), i=i, t=t, t→t, e→i (replace), n→n, +g (insert) Step by step: kitten → sitten (replace k with s) → sittin (replace e with i) → sitting (insert g) Answer: 3 operations

Quick Quiz

1. What two properties must a problem have to be solvable with dynamic programming?

  • a) Greedy choice property and optimal substructure
  • b) Optimal substructure and overlapping subproblems
  • c) Divide and conquer with no overlapping subproblems
  • d) Polynomial time and constant space
Answer

b) Optimal substructure and overlapping subproblems — Optimal substructure means the optimal solution contains optimal solutions to subproblems. Overlapping subproblems means the same subproblems are solved multiple times, making caching beneficial.

2. What is the key difference between top-down (memoization) and bottom-up (tabulation) DP?

  • a) Top-down is always faster
  • b) Top-down uses recursion with caching; bottom-up fills a table iteratively
  • c) Bottom-up cannot be space-optimized
  • d) Top-down solves all subproblems; bottom-up only solves needed ones
Answer

b) Top-down uses recursion with caching; bottom-up fills a table iteratively — Top-down starts from the main problem and recurses downward. Bottom-up builds from the smallest subproblems upward. Top-down may skip unneeded subproblems but risks stack overflow.

3. What is the time complexity of the 0/1 Knapsack problem with items and capacity ?

  • a)
  • b)
  • c)
  • d)
Answer

b) — The DP table has entries, each computed in . Note this is pseudo-polynomial: polynomial in the value of , not in the number of bits to represent it.

4. In the space-optimized 0/1 Knapsack, why must you iterate the capacity in reverse?

  • a) To sort the items by weight
  • b) To prevent using the same item more than once in the same row
  • c) To improve cache performance
  • d) To reduce the number of iterations
Answer

b) To prevent using the same item more than once in the same row — Forward iteration would use the already-updated values from the current row, effectively allowing item reuse (which is the unbounded knapsack). Reverse iteration ensures you only reference values from the previous row.

5. Which DP pattern best describes the Edit Distance problem?

  • a) 1D linear sequence
  • b) 2D two-sequence comparison
  • c) Interval DP
  • d) Bitmask DP
Answer

b) 2D two-sequence comparison — Edit distance compares two strings character by character, with state dp[i][j] representing the edit distance between the first characters of one string and the first characters of the other.

Lessons: next — DP Foundations · module — Dynamic Programming · course — DSA: Zero to Mastery. Previous module: Module 5 · Paradigms. Next module: String Algorithms.