Stop 18 · Data Structures & AlgorithmsTopics · 15/17

Dynamic Programming

Part of the Full Stack Developer Roadmap

In short

Dynamic programming has a scary name for a simple habit: never solve the same small problem twice. Write the answer down, reuse it, and slow recursion becomes fast.

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 purple blob climbs stairs, sticking a note on each step it has worked out.

Think of it like this

Sticky notes on the staircase

How many ways can you climb to step 5, taking 1 or 2 steps at a time? Work out step 1, stick a note on it. Step 2, another note. Each new step just adds the notes on the two steps below.

Watch it happen

Filling the table for climbStairs(5)

1/5dp[i] = ways to reach step i. Step 0 and step 1 each have exactly 1 way.

The big ideas

What you need to know

Overlapping subproblems

If plain recursion keeps calling the same inputs again, like fib(3) many times, DP can help.

Optimal substructure

The best answer for n can be built from best answers for smaller inputs.

Top-down: memoise

Keep your recursion and cache results in a Map. Easiest to write from a brute-force solution.

Bottom-up: fill a table

Start from the smallest cases and fill an array upward. No recursion, no stack limits.

See it in code

Walk through the code

1// Ways to climb n steps taking 1 or 2 at a time2function climbStairs(n: number): number {3  const dp = new Array(n + 1).fill(0);4  dp[0] = 1;                       // one way to stay at the bottom5  dp[1] = 1;6  for (let i = 2; i <= n; i++) {7    dp[i] = dp[i - 1] + dp[i - 2]; // last move was 1 step or 2 steps8  }9  return dp[n];10}11 12console.log(climbStairs(5)); // 8

1/3Make the table and fill in the base cases you know for sure.

Plain recursion here is O(2ⁿ). The table makes it O(n). You only ever need the last two values, so it can even be O(1) space.

Save yourself the pain

Common mistakes

Oops

Jumping straight to the table without knowing what dp[i] means.

Do this instead

Write one sentence first, like "dp[i] is the number of ways to reach step i". The code follows from it.

Oops

Getting base cases wrong, so every later cell is off.

Do this instead

Check dp[0] and dp[1] by hand on a tiny input before running anything.

Your mission

From recursion to DP

~45 min

Quick check

When is dynamic programming most likely to help?

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.