How 1D DP works

Before you start

• Recursion

  Fibonacci's call tree repeats the same calls, and memoization stores each answer once. Climbing Stairs is the same recurrence.

  Open lesson

Why it matters

Counting routes, schedules, or action sequences often produces the same smaller question through many different histories. A direct recursive model can be correct yet become unusable because those histories multiply exponentially. The number of ways to reach step n must be computed without solving the same smaller stair count more than once.

You can climb 1 or 2 steps at a time. Return how many distinct ways you can climb n steps.

Input

n = 5

Output

8

For n = 5, plain recursion reaches climbStairs(3) through multiple branches. Fill [1, 1, 2, 3, 5, 8] once from left to right instead, replacing the brute call tree with one addition per new step.

For n = 5, ways[0] = 1 represents doing nothing and ways[1] = 1 represents one single step. Step 2 can be entered from 1 or 0, so ways[2] = 1 + 1 = 2.

Continue left to right: ways[3] = 2 + 1 = 3, ways[4] = 3 + 2 = 5, and ways[5] = 5 + 3 = 8. Each cell reads the two completed cells before it, so no recursive call or unfinished dependency remains.