How is it related to Fibonacci?

To reach the Nth stair, you can either come from (N-1) by taking 1 step OR from (N-2) by taking 2 steps. Thus, Ways(N) = Ways(N-1) + Ways(N-2).

Adding more step options?

If you can take 1, 2, or 3 steps, the relation becomes Ways(N) = Ways(N-1) + Ways(N-2) + Ways(N-3).

Is it Top-Down or Bottom-Up?

Both work! Top-down says "I can come from below." Bottom-up says "From here, I can go higher."

Climbing Stairs

The Climbing Stairs problem asks for the number of distinct ways to reach the top of a staircase when you can take 1 or 2 steps at a time.

READY

Initialize DP array of size 6

Base Cases: dp[0]=1 (Ground), dp[1]=1 (1 Step)

Stairs

Intuition

If you are at step n, you must have come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). Thus, the number of ways to reach step n is simply the sum of ways to reach the two previous steps. This structure is identical to the Fibonacci sequence.

Concept

Recurrence Relation:

Ways(n) = Ways(n-1) + Ways(n-2)

Base Cases:

Ways(0) = 1 (Standing on the ground is 1 way)
Ways(1) = 1 (One step to reach step 1)
Ways(2) = 2 (1+1 or 2)

This is a classic 1D Dynamic Programming problem where the state depends only on the previous two states.

How it Works

Tabulation Algorithm:

Initialize an array dp of size n+1.
Set dp[0] = 1, dp[1] = 1.
Iterate from i = 2 to n.
For each step, set dp[i] = dp[i-1] + dp[i-2].
The answer is dp[n].

Step-by-Step Breakdown

Visualizing the path:

Step 0 & 1: Fixed starting points.
Step 2: Sum of Step 1 and Step 0.
Step 3+: Rolling sum of the previous two values.

When to Use

Applications:

Counting permutations with restricted step sizes.
Foundation for more complex "path counting" problems (e.g., Min Cost Climbing Stairs).

When NOT to Use

Variable Steps: If step sizes change dynamically, the simple 2-state relation breaks (though DP still applies with modification).

How to Identify

"Count distinct ways", "Review previous choices".

Sample Problems

Min Cost Climbing Stairs

Minimize cost to reach top.

Decode Ways

Similar pattern but with conditional transitions.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Fibonacci Sequence

Unique Paths