Dynamic Programming Pattern

Why this pattern matters for LeetCode

The brute-force for Climbing Stairs recurses into ways(n-1) and ways(n-2) at every call. ways(n-2) gets computed once directly from ways(n), once inside ways(n-1), and again inside each of those — the same subproblem is recomputed exponentially. Dynamic programming notices that overlapping subproblems repeat and stores each answer the first time it's computed. Every subproblem is solved exactly once. The exponential blowup collapses to O(n).

What the Dynamic Programming pattern is

Dynamic programming builds a solution by combining answers to smaller, overlapping subproblems. For 1D problems, dp[i] holds the answer for the subproblem at index i. You define a recurrence — how dp[i] is built from dp[i-1], dp[i-2], or earlier values — then fill the array from the smallest subproblem up. The answer is usually dp[n] or dp[n-1]. If the recurrence only looks back one or two steps, you can replace the full array with rolling variables and reduce space to O(1).

Reach for Dynamic Programming when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Dynamic Programming

• ✓Counting the number of distinct ways to reach a goal (Climbing Stairs, Decode Ways)
• ✓Finding the minimum cost or maximum value to reach the end of an array (House Robber, Coin Change)
• ✓Problems with a 'take it or leave it' decision at each step where past choices constrain future ones
• ✓Any recursive brute force that produces an exponential call tree with repeated subproblems

When NOT to use Dynamic Programming

• ✕Subproblems don't overlap — each recursive path is unique. Plain recursion works fine.
• ✕A greedy choice always leads to the global optimum without needing to revisit past decisions
• ✕You need to enumerate all solutions, not just the optimal one — backtracking handles that
• ✕The state at each step depends on more than a fixed window of previous values — 2D DP may be needed

Better alternative: In those cases, Greedy (when a local optimum is always globally optimal) or Backtracking (when you need all solutions) is more appropriate.

JavaScript code template

Climbing Stairs — O(n) time, O(1) space

function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1; // ways to reach step 1
  let prev1 = 2; // ways to reach step 2

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

  return prev1;
}

To reach step i, you came from step i-1 (one step up) or step i-2 (two steps up). So ways[i] = ways[i-1] + ways[i-2] — the Fibonacci recurrence. Base cases: 1 way to reach step 1, 2 ways to reach step 2. Because the recurrence only looks back two steps, two rolling variables replace the full dp array. Each iteration: compute the new value, shift prev1 into prev2, assign the new value to prev1. After the loop, prev1 holds the answer.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Define what dp[i] means: 'the answer for the subproblem at index i' — be specific about what the index represents.
2. 2Write the recurrence: how does dp[i] depend on dp[i-1], dp[i-2], or earlier values?
3. 3Identify the base cases: the smallest subproblems you can answer directly, without the recurrence.
4. 4Fill dp[] from left to right, starting from the base cases.
5. 5Return dp[n] or dp[n-1] depending on your indexing.
6. 6If the recurrence looks back only one or two steps, replace the array with rolling variables to get O(1) space.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Climbing Stairs

  ways[i] = ways[i-1] + ways[i-2] — the textbook 1D DP recurrence, structurally identical to Fibonacci.

  Premium→
• House Robber

  At each house: rob it (nums[i] + dp[i-2]) or skip it (dp[i-1]). Take the max. Adjacent houses can't both be robbed.

  Premium→
• Coin Change

  dp[amount] = minimum coins needed. For each coin denomination: dp[i] = min(dp[i], dp[i - coin] + 1).

  Premium→

Coming soon

• Min Cost Climbing Stairs

  dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Pay the cost at each step, then choose the cheaper of the two ways to climb from it.

  Coming soon
• Decode Ways

  dp[i] = ways to decode the first i characters. At each position, check valid 1-digit and 2-digit decodings and accumulate from earlier dp values.

  Coming soon

Common mistakes beginners make

• ✕Skipping the base cases — without dp[0] and dp[1] defined, the recurrence has nothing to build from.
• ✕Initializing dp to zero when zero isn't a valid answer for the base case — read the problem constraints carefully.
• ✕Keeping the full O(n) dp array when two rolling variables would do — if the recurrence only looks back 1 or 2 steps, you don't need the whole array.
• ✕Confusing DP with Greedy — DP tries all subproblem combinations and keeps the best; Greedy takes the locally best option at each step without reconsidering. If a greedy choice always works, you don't need DP.

Dynamic Programming vs Greedy vs Backtracking

Choose the right tool for the job.

Time and space complexity

You fill each cell dp[i] exactly once using a constant number of lookups. The loop runs n times, each step is O(1) — total O(n). If the recurrence looks back only one or two steps, two variables replace the array and space drops to O(1). When dp[i] depends on all previous values (like in Coin Change), you need the full O(n) array.

Frequently asked questions

How do I know if a problem needs dynamic programming?

Ask two questions: 'Does the brute-force recursion compute the same subproblem more than once?' and 'Can I define dp[i] as the answer for a subproblem of size i, expressed in terms of smaller subproblems?' If both are true, DP applies. The clearest signal is an exponential recursion tree where identical calls appear at multiple branches.

What's the difference between top-down and bottom-up DP?

Top-down (memoization) uses recursion — compute a subproblem the first time, cache the result, and return the cached value on future calls. Bottom-up (tabulation) fills a dp array iteratively from smallest to largest, no recursion at all. Both give the same answer. Bottom-up avoids recursion overhead and is easier to optimize for space — you can often replace the array with rolling variables.

Why does Climbing Stairs have the same recurrence as Fibonacci?

Because the structure is identical: to reach step n, you came from step n-1 or step n-2. So ways(n) = ways(n-1) + ways(n-2) — exactly the Fibonacci recurrence. The base cases differ (ways(1) = 1, ways(2) = 2 instead of fib(1) = 1, fib(2) = 1), but the logic is the same. Recognizing this means you already know the template.

When can I reduce the dp array to rolling variables?

When dp[i] only depends on a fixed number of previous values — usually just dp[i-1] and dp[i-2]. Replace the array with two variables (prev1 and prev2), update them at each step, and space drops from O(n) to O(1). If dp[i] depends on all previous values, like in Coin Change, you need the full array.