Dynamic Programming

How It Works

Dynamic programming (DP) solves a problem by defining a state, usually "the answer for the first i elements" or "the answer ending at index i", and a transition that computes each state from smaller, already-solved states. The key requirement is that the problem has overlapping subproblems (the same smaller problem gets solved repeatedly in a naive recursive approach) and optimal substructure (the optimal answer to the whole problem can be built from optimal answers to its subproblems).

There are two equivalent ways to implement it. Top-down (memoization) keeps the natural recursive structure but caches the result of each state the first time it's computed, so repeat calls are O(1) lookups instead of full recursions. Bottom-up (tabulation) flips this around: it fills an array iteratively from the smallest state upward, so every state is computed exactly once with no recursion or call-stack overhead at all.

Once you can write the recurrence relation (how dp[i] depends on dp[i-1], dp[i-2], etc.), the rest is mechanical: initialize the base cases, iterate through the states in dependency order, and read the final answer off the last state (or the max/min across all states, depending on the problem).

When To Use It

• "Minimum/maximum/count of ways" questions: coin change (minimum coins), climbing stairs (count of ways), house robber (maximum non-adjacent sum) all ask for an optimal value, not just any valid answer.
• Brute-force recursion recomputes the same subproblem repeatedly: if you sketch a recursive solution and notice fib(5) gets called from both fib(6) and fib(7), that overlap is the signal.
• Decisions build on prior decisions: longest increasing subsequence and longest common subsequence both define dp[i] in terms of comparisons against earlier indices.
• Greedy provably fails: if picking the "locally best" option at each step can lock you into a worse overall answer (unlike in genuinely greedy problems), DP considers all options and keeps the best.
• The problem can be phrased as "yes/no reachability" over states: word break asks "can I reach the end of the string using dictionary words," which maps directly onto a boolean DP array.

Time & Space Complexity

Most 1D DP problems (climbing stairs, house robber, coin change, maximum subarray) run in O(n) time and can be optimized to O(1) space by keeping only the last one or two states instead of the full array. Problems comparing pairs of indices (longest increasing subsequence in its simple form, longest common subsequence) run in O(n^2) time and O(n) or O(n*m) space for the DP table. LIS can be optimized to O(n log n) using patience sorting with binary search.

// Bottom-up 1D DP template
function solve(nums) {
  const n = nums.length;
  if (n === 0) return 0;

  const dp = new Array(n).fill(0);
  dp[0] = baseCase(nums[0]);

  for (let i = 1; i < n; i++) {
    dp[i] = transition(dp[i - 1], nums[i]); // e.g. Math.max(dp[i-1] + nums[i], nums[i])
  }

  return dp[n - 1]; // or Math.max(...dp), depending on the problem
}

Alternative Approaches

• Memoized recursion vs. bottom-up tabulation: memoization is easier to derive directly from the brute-force recursive solution and only computes states that are actually reachable; tabulation avoids recursion overhead and stack-depth limits but computes every state up front, even unreachable ones.
• Space-optimized rolling variables: when dp[i] only depends on the last one or two entries (climbing stairs, house robber), replace the whole array with two or three scalar variables to cut space from O(n) to O(1).
• Binary search optimization: longest increasing subsequence has an O(n log n) variant using a "tails" array and binary search, trading the intuitive O(n^2) DP for a less obvious but much faster approach.
• Greedy as a special case: some problems that look like they need DP (activity selection, some interval problems) actually have a provably optimal greedy solution; always check whether a proof of the greedy-choice property exists before defaulting to DP.

Common Mistakes

• Wrong base case: off-by-one errors in dp[0] or dp[1] propagate through every subsequent state and are the most common source of DP bugs.
• Confusing "ending at i" with "using first i elements": these are subtly different state definitions (e.g. maximum subarray vs. longest increasing subsequence) and mixing them up breaks the transition.
• Not initializing unreachable states correctly: coin-change style problems need Infinity (or a sentinel) for "unreachable," not 0, or the min/max comparisons silently produce wrong answers.
• Iterating in the wrong order: bottom-up DP requires that every state you read has already been computed; iterating in the wrong direction reads garbage or stale values.
• Recomputing without memoizing in a "recursive" solution: writing recursion without a cache is just brute force wearing a DP-shaped costume, and will time out on larger inputs.

Pattern Summary

Dynamic programming is the answer whenever a problem asks for an optimal value or count over a sequence and a brute-force recursive solution would recompute the same subproblems repeatedly. Define the state, write the recurrence relating it to smaller states, pick memoization or tabulation, and mind your base cases: that combination turns exponential brute force into a solution that runs in polynomial time and space.