Skip to main content

🧠 Dynamic Programming

One-line summary: Break a problem into overlapping subproblems, solve each once — turning exponential time into polynomial.

Diagram​

Dynamic Programming GIF

🎯 Concept​

Dynamic Programming (DP) solves complex problems by breaking them into simpler subproblems, solving each subproblem once, and storing (caching) the result. Apply DP when a problem has both:

  1. Optimal substructure: the optimal solution is built from optimal solutions of its subproblems.
  2. Overlapping subproblems: the same subproblem is computed many times by a naive recursion.
flowchart TD
    A["Naive recursion\nexponential, recomputes"] --> B{"Overlapping\nsubproblems?"}
    B -->|Yes| C["Add caching"]
    C --> D["Top-Down\n(Memoization)\nrecursion + cache"]
    C --> E["Bottom-Up\n(Tabulation)\niterative table"]
    D --> F["Polynomial time"]
    E --> F

Top-Down vs Bottom-Up​

AspectTop-Down (Memoization)Bottom-Up (Tabulation)
StyleRecursion + cacheIterative table filling
OrderSolves on demandSolves all states in order
SpaceO(states) + call stackO(states), often space-optimizable
IntuitionEasier to write from recurrenceFaster, no recursion overhead

Common DP Categories​

1D DP · 2D / grid DP · Knapsack (take / not-take) · LIS · LCS / DP on strings · DP on stocks · Partition / interval DP · Bitmask DP.

⚡ Time & Space Complexity​

PatternTimeSpace
1D DP (house robber, climb stairs)O(n)O(1) optimised
2D DP (grid / string)O(m·n)O(n) row-optimised
0/1 KnapsackO(n·W)O(W)
LIS (DP)O(n²)O(n)
LIS (patience/binary search)O(n log n)O(n)
LCSO(m·n)O(m·n)

Key Insight: The number of distinct states × work per state = total time. Optimize space by keeping only the states you still need (e.g., last row/two variables).

Common Patterns​

1D DP — House Robber​

function rob(nums) {
  let prev2 = 0,
    prev1 = 0;
  for (const n of nums) {
    const curr = Math.max(prev1, prev2 + n);
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
// State: best loot up to house i. Time O(n), Space O(1).

2D DP — Edit Distance (Levenshtein)​

function editDistance(w1, w2) {
  const m = w1.length,
    n = w2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)),
  );
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] =
        w1[i - 1] === w2[j - 1]
          ? dp[i - 1][j - 1]
          : 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
  return dp[m][n];
}
// Time O(m*n), Space O(m*n).

0/1 Knapsack — take / not-take​

function knapsack(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < weights.length; i++)
    for (let w = W; w >= weights[i]; w--)
      // iterate backwards for 0/1
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
  return dp[W];
}
// Time O(n*W), Space O(W).

LIS — Longest Increasing Subsequence O(n log n)​

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0,
      hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x;
  }
  return tails.length;
}
// Binary search keeps the smallest tail per length. Time O(n log n).

🧪 Worked Example: Coin Change (min coins)​

Given coin denominations and an amount, find the fewest coins to make it.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0 coins to make amount 0
  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}
// dp[a] = fewest coins to form amount a. Time O(amount * coins), Space O(amount).

Recurrence: dp[a] = min(dp[a - coin] + 1) over all coins that fit — optimal substructure (best for a uses the best for a - coin) and overlapping subproblems (dp[a - coin] reused).

Pitfalls​

  • Wrong iteration order: 0/1 knapsack must iterate capacity backwards; unbounded knapsack forwards.
  • Uninitialized base cases: forgetting dp[0] leads to wrong answers.
  • Not space-optimizing: many 2D DPs only need the previous row.
  • Confusing subsequence vs substring: contiguity changes the recurrence.

Practice Problems​

ProblemDifficultySolution
LC 70 — Climbing StairsEasy
LC 121 — Best Time to Buy and Sell StockEasy
LC 198 — House RobberMedium
LC 322 — Coin ChangeMedium
LC 300 — Longest Increasing SubsequenceMedium
LC 1143 — Longest Common SubsequenceMedium

| LC 62 — Unique Paths | Medium | | | LC 63 — Unique Paths II | Medium | | | LC 64 — Minimum Path Sum | Medium | | | LC 91 — Decode Ways | Medium | | | LC 96 — Unique Binary Search Trees | Medium | | | LC 120 — Triangle | Medium | | | LC 139 — Word Break | Medium | | | LC 152 — Maximum Product Subarray | Medium | | | LC 213 — House Robber II | Medium | | | LC 221 — Maximal Square | Medium | | | LC 279 — Perfect Squares | Medium | | | LC 300 — Longest Increasing Subsequence | Medium | | | LC 309 — Best Time to Buy and Sell Stock with Cooldown | Medium | | | LC 322 — Coin Change | Medium | | | LC 338 — Counting Bits | Medium | | | LC 343 — Integer Break | Medium | | | LC 377 — Combination Sum IV | Medium | | | LC 416 — Partition Equal Subset Sum | Medium | | | LC 494 — Target Sum | Medium | | | LC 516 — Longest Palindromic Subsequence | Medium | | | LC 518 — Coin Change 2 | Medium | |

| LC 740 — Delete and Earn | Medium | | | LC 931 — Minimum Falling Path Sum | Medium | |

| LC 42 — Trapping Rain Water | Hard | | | LC 44 — Wildcard Matching | Hard | | | LC 72 — Edit Distance | Hard | | | LC 85 — Maximal Rectangle | Hard | | | LC 87 — Scramble String | Hard | | | LC 115 — Distinct Subsequences | Hard | | | LC 123 — Best Time to Buy and Sell Stock III | Hard | | | LC 132 — Palindrome Partitioning II | Hard | | | LC 140 — Word Break II | Hard | | | LC 188 — Best Time to Buy and Sell Stock IV | Hard | | | LC 312 — Burst Balloons | Hard | | | LC 329 — Longest Increasing Path in a Matrix | Hard | | | LC 354 — Russian Doll Envelopes | Hard | | | LC 410 — Split Array Largest Sum | Hard | | | LC 446 — Arithmetic Slices II - Subsequence | Hard | | | LC 472 — Concatenated Words | Hard | | | LC 546 — Remove Boxes | Hard | | | LC 664 — Strange Printer | Hard | | | LC 689 — Maximum Sum of 3 Non-Overlapping Subarrays | Hard | | | LC 1000 — Minimum Cost to Merge Stones | Hard | | | LC 1092 — Shortest Common Supersequence | Hard | | | LC 1235 — Maximum Profit in Job Scheduling | Hard | | | CC — LCS (LCSSTR) | Hard | | | CC — Advanced DP (ADVDP) | Hard | | | CC — Matrix Chain Multiplication (MATCHAIN) | Hard | |

← Back to Home · © sparshjaswal

Last updated on