Skip to content

Dynamic Programming Deep Dive

Learn the DP paradigm: optimal substructure, overlapping subproblems, tabulation, and memoization.

What you'll learn

  • Optimal substructure and overlapping subproblems
  • Top-down memoization vs bottom-up tabulation
  • State design and transition equations
  • Space optimization with rolling arrays

Concept

Dynamic Programming Deep Dive

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems and storing results to avoid recomputation. Two properties must hold: optimal substructure (the optimal solution contains optimal solutions to subproblems) and overlapping subproblems (the same subproblems recur repeatedly).

Top-Down vs Bottom-Up

Top-down (memoization) starts from the original problem and recurses downward, caching results. It is natural to write but uses recursion (stack risk). Bottom-up (tabulation) fills a table from the smallest subproblems up. It is iterative and often faster due to no recursion overhead.

State Design

The hardest part of DP is defining the state - what information captures a subproblem. For the knapsack problem, state is (item index, remaining capacity). For edit distance, state is (position in string A, position in string B). Good state design makes the transition natural.

Transition Equation

The transition expresses how to build a larger solution from smaller ones. For LCS: dp[i][j] = dp[i-1][j-1] + 1 if A[i]=B[j], else max(dp[i-1][j], dp[i][j-1]). Writing the transition is the core of DP.

Space Optimization

If dp[i] only depends on dp[i-1], you can use a rolling array of size 2 instead of the full table, reducing space from O(n^2) to O(n).

Example

              // Edit distance (Levenshtein) - bottom-up DP
function editDistance(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  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 (a[i-1] === b[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
  }
  return dp[m][n];
}
// 0/1 Knapsack with rolling array
function knapsack(wt, val, cap) {
  let prev = new Array(cap+1).fill(0);
  for (let i = 0; i < wt.length; i++) {
    const curr = new Array(cap+1).fill(0);
    for (let w = 0; w <= cap; w++) {
      curr[w] = prev[w];
      if (wt[i] <= w) curr[w] = Math.max(curr[w], prev[w-wt[i]] + val[i]);
    }
    prev = curr;
  }
  return prev[cap];
}
console.log('Edit distance:', editDistance('kitten', 'sitting'));
console.log('Knapsack:', knapsack([2,3,4,5], [3,4,5,6], 8));
            

Edit distance fills a 2D table where dp[i][j] is the cost of converting a[:i] to b[:j]. Knapsack uses a rolling array - only the previous row is needed, halving memory.

Try it

  • Code Diff

    Compare recursive vs DP solutions to see how memoization transforms exponential to polynomial time.

Common mistakes

The mistake

Using the wrong DP direction - filling the table in an order that uses uninitialized values.

The fix

Ensure each cell's dependencies are filled before it. In bottom-up, iterate in increasing order of subproblem size.

The mistake

Not recognizing a problem as DP.

The fix

If a problem asks for the best way or number of ways and has overlapping subproblems, it is likely DP.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors