parikshan

climbing-stairs

Difficulty: Easy  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/climbing-stairs/start

The story

A robotics team is testing a delivery bot that climbs stairs in 1-step or 2-step strides. Given a flight of n stairs, the operations lead asks: "how many distinct stride sequences land us at step n exactly?" The team needs the count to log valid sequences for a regulator. They send you n and want the count.

The answer is the n-th Fibonacci number, and the discovery that it is the Fibonacci number is the entire lesson. Once you see this, you will recognise Fibonacci-shaped recurrences in places nobody calls Fibonacci: counting routes through a state graph, counting password formats, counting tile arrangements, counting valid messages of length n.

What's actually being asked

You climb a staircase of n steps. You can step 1 stair or 2 stairs at a time. How many distinct ways can you reach step n?

Examples:

  • n=1 → 1 way: (1).
  • n=2 → 2 ways: (1+1), (2).
  • n=3 → 3 ways: (1+1+1), (1+2), (2+1).
  • n=4 → 5 ways: (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2).
  • n=5 → 8 ways.

The sequence 1, 2, 3, 5, 8, 13, 21, ... is Fibonacci shifted by one.

The naive approach

Brute-force recursion:

def ways(n):
    if n == 0: return 1
    if n == 1: return 1
    return ways(n - 1) + ways(n - 2)

Correct but exponential. For n=40, this recomputes Fibonacci values billions of times. For n=100, the heat death of the universe arrives first.

The key insight

To reach step n, your last move was either a 1-step (from step n-1) or a 2-step (from step n-2). The total ways is therefore ways(n-1) + ways(n-2). That recurrence is the entire problem.

The reason brute-force is slow is that the same subproblems are recomputed exponentially. Memoise (cache the results) or, better, build up bottom-up with a 1-D array. Each value is computed once.

This is the gateway DP. The four DP questions:

  1. State: dp[i] = number of ways to reach step i.
  2. Base case: dp[0] = 1 (one way to be at the bottom: do nothing). dp[1] = 1.
  3. Transition: dp[i] = dp[i-1] + dp[i-2].
  4. Answer: dp[n].

Step-by-step approach

Bottom-up, O(n) time, O(n) space:

def climb(n):
    if n <= 1: return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Notice that dp[i] depends only on the previous two values. Collapse the array to two variables:

def climb(n):
    if n <= 1: return 1
    a, b = 1, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

O(n) time, O(1) space.

Worked example

n = 5
ia (i-2)b (i-1)new b = a+b
2112
3123
4235
5358

Return 8. ✓

Complexity

  • Time: O(n) for both versions.
  • Space: O(n) for the array version, O(1) for the two-variable version.

For absurdly large n (say, 10⁸), you can compute Fibonacci in O(log n) with fast matrix exponentiation. Out of scope for this article, but worth knowing the trick exists.

Common pitfalls

  • Off-by-one in the base case: dp[0]'s meaning matters. If you define dp[i] as "ways starting from step i to reach the top", you get a different recurrence. Pick one definition and stick with it.
  • Using the brute-force recursion in production: for n=50 it will hang. The fix is one decorator (@lru_cache) or a 4-line loop.
  • Integer overflow in languages with bounded integers: Fibonacci grows exponentially. For n=92, the value exceeds 2⁶³. Python is fine; in Java or Go, use BigInteger or long with a modulo.

Where this shows up in the enterprise

  • A/B test traffic allocation: counting valid bucket assignments under "no consecutive same bucket" reduces to a Fibonacci-shaped recurrence.
  • Phone number / OTP combinatorics: counting valid 6-digit codes with adjacency rules; same recurrence shape.
  • Network protocol message framing: counting valid frames of length n given the allowed byte transitions.
  • Stripe billing: counting valid invoice schedules under a "no two charges within X days" constraint.
  • Game level design: counting paths through a tile-board with limited move types.
  • DNA sequence counting in bioinformatics: number of valid codon sequences of length n with constraints.
  • Pricing rule combinations: counting valid combinations of coupons that respect adjacency rules.
  • Compliance check on event sequences: counting valid orderings of n events under "no two of the same type adjacent".

Whenever a problem asks "how many ways to do X with a constraint that depends on the last one or two moves", the answer is a Fibonacci-shaped DP.

Variants you'll see elsewhere

  • min-cost-climbing-stairs: add a cost to each step; minimise total cost. Same recurrence with min instead of +.
  • house-robber: cannot rob adjacent houses; the recurrence is dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Pick-or-skip flavour.
  • decode-ways: count decodings of a digit string under a mapping. The recurrence considers one-digit and two-digit decodes from the right.
  • tribonacci: 3-term recurrence; same shape.
  • unique-paths: 2-D generalisation; dp[i][j] = dp[i-1][j] + dp[i][j-1].

Once Fibonacci clicks, this whole family clicks at once.

How parikshan turns this into a learning loop

DP is where the integrated learning loop pays its highest dividends. The pattern from this point on:

  1. Read this article. The recurrence is the entire idea.
  2. Solve in practice mode with no AI. Force yourself to write the recurrence as a comment first, then the code. This is the muscle that transfers.
  3. AI training: Optimise your solution. The assistant should produce the O(1) space version. If your version was already O(1), good; it should say "already optimal". This is how you calibrate the assistant: if it pushes a worse solution, ignore it.
  4. Move to min-cost-climbing-stairs and house-robber in sequence. Both reuse this recurrence's shape with one change. Solve both in exam mode with the proctor on; the bank's dynamic tests on house-robber include adversarial inputs that catch the picks-adjacent error.
  5. Dispute flow is rarely needed for DP problems (verdicts are unambiguous), but if you believe your O(n) algorithm should not TLE on a stress test, dispute it. A human reviewer can recalibrate the time limit if the bank's reference is off.

That four-step loop is the entire pedagogical core of parikshan: independent attempt, then graduated AI help with cost, then integrated review.

In the AI-integrated workspace

DP is the algorithm class where AI agents are simultaneously the most useful and the most dangerous.

Useful because once you give the agent the recurrence, it produces correct code in 10 seconds in any language you ask. State the recurrence, get the code.

Dangerous because if you let the agent invent the recurrence, it will sometimes give you a plausible-looking but subtly wrong one. The classic error: agents off-by-one on the base case, or invert min/max, or pick the wrong starting value (0 vs. -infinity vs. 1).

The 2027 engineer's discipline:

  1. State the recurrence in English before the agent codes. "dp[i] is the number of ways to reach step i. dp[i] = dp[i-1] + dp[i-2]. dp[0] = dp[1] = 1."
  2. Tell the agent to implement that recurrence. Not "solve climbing stairs"; tell it the recurrence.
  3. Verify on n=5 by hand. Always.
  4. Ask the agent to collapse memory. "Reduce to O(1) space using two variables."

That discipline turns a probabilistic answer into a deterministic, verified one. parikshan's loop is built to train exactly that discipline.

climbing-stairs