Stop 21 · Data Structures & AlgorithmsTopics · 15/17

Dynamic Programming

In short

DP has a scary reputation, but the core idea is simple: don't solve the same small problem twice. Write the answer down once and look it up next time.

Solving complex problems by breaking them into overlapping subproblems, solving each once, and reusing the cached results — arguably the hardest, most feared interview topic.

The jaadu at an exam desk glances at a small formula sheet beside the answer booklet.

Think of it like this

Your exam formula sheet

Deriving the same formula in every question wastes your three hours. So you derive it once, write it on your sheet, and reuse it. DP is that sheet: save each small answer, reuse it for bigger ones.

Watch it happen

Ways to climb 6 stairs

1/5Base cases: 1 way to reach step 1, and 2 ways to reach step 2 (1 + 1, or 2).

The big ideas

What you need to know

Overlapping subproblems

Plain recursive Fibonacci recomputes fib(3) again and again. That repeat work is what DP removes.

Build big from small

The answer for n comes from answers for smaller inputs, like dp[n] = dp[n-1] + dp[n-2].

Top-down or bottom-up

Top-down is recursion plus a memo (cache). Bottom-up fills a table from the smallest case upwards.

Shrink the table

If each step only needs the last two values, keep two variables instead of a whole array.

How it works

Solving any DP question

1
Define the state
Say in words what dp[i] means, like 'ways to reach step i'.
2
Find the recurrence
How does dp[i] come from smaller states?
3
Set base cases
Fill in the smallest answers you know directly.
4
Fill in order
Compute from small to big so every value you need is ready.
5
Trim memory
Keep only the states you still need.

See it in code

Walk through the code

1// Climbing Stairs: take 1 or 2 steps. How many ways to reach step n?2function climbStairs(n) {3  if (n <= 2) return n;4  let prev2 = 1; // ways to reach step 15  let prev1 = 2; // ways to reach step 26 7  for (let i = 3; i <= n; i++) {8    const curr = prev1 + prev2;9    prev2 = prev1;10    prev1 = curr;11  }12  return prev1;13}

1/4Small inputs are answered directly.

You reach step i from step i-1 or i-2, so ways add up. One loop gives O(n) time and two variables give O(1) space. Plain recursion would be exponential.

Save yourself the pain

Common mistakes

Oops

Jumping into code before writing what dp[i] means.

Do this instead

Write the state in one plain sentence first. Most DP bugs come from a fuzzy state.

Oops

Starting with hard problems like 'Edit Distance' on day one.

Do this instead

Start with Climbing Stairs, House Robber and Coin Change. The patterns repeat in the hard ones.

Your mission

First three DP problems

~45 min

Quick check

You add a memo (cache) to recursive Fibonacci. What's the new time complexity for fib(n)?

Go deeper

1Start with classic DP problems: climbing stairs, coin change, longest common subsequence.
2Practice both memoization (top-down) and tabulation (bottom-up) for the same problem.
3Learn to first write the brute-force recursive solution, then optimize with a cache.