Easy–medium · intro DP

Climbing Stairs

Think about the last move, not the first: to stand on stair n you came from n−1 or n−2, and those two journeys never overlap in their final step. That single sentence is the whole algorithm.

At a glanceways(n) = ways(n-1) + ways(n-2), with ways(1) = 1 and ways(2) = 2 — carry just two variables up the ladder.

Problem

Input: One integer n (1 ≤ n ≤ 40), the number of stairs.

Output: The number of distinct ways to reach stair n taking 1 or 2 steps at a time.

Samples:

Input	Output
`3`	`3`
`5`	`8`

For n = 3 the ways are 1+1+1, 1+2 and 2+1 — the order of your steps matters, which is why 2+1 is not the same journey as 1+2.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Reason from the last move

Every journey to stair n ends with a final step of size 1 (from n−1) or size 2 (from n−2). The two groups cannot overlap, and together they are all journeys — so ways(n) = ways(n-1) + ways(n-2). When an argument starts with "look at the last move", dynamic programming is usually hiding nearby.

Hint 2 — Nail the base cases

ways(1) = 1 (one way: 1) and ways(2) = 2 (1+1, or 2). Write them before the loop and check the smallest inputs by hand — most wrong answers in this problem are a base case that is off by one, not a broken recurrence.

Hint 3 — Two variables are enough

The recurrence only ever looks one and two steps back, so keep a = ways(k-1) and b = ways(k), and roll them up in a loop: c = a + b; a = b; b = c;. No array, no recursion — and no risk of the exponential blowup a naive recursive version suffers.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a = 1, b = 2;   // ways(1), ways(2)
    if (n == 1) { cout << 1 << endl; return 0; }
    for (int k = 3; k <= n; k++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << endl;
    return 0;
}

You have just written your first dynamic program: a recurrence, base cases, and a bottom-up fill. The same three pieces solve Fibonacci (it is literally the same numbers), and later they will solve tables like Minimum Path Sum. The habit worth keeping: derive the recurrence from the last move, then trust it all the way down.

Deep dive

Why this works

Ask what the last move was, not the first: every journey to stair n arrives from n-1 (a 1-step) or n-2 (a 2-step), and those two families are disjoint and exhaustive. So ways(n) = ways(n-1) + ways(n-2) — the definition of a DP where the answer for n is built from smaller answers already known.

The cost

O(n) time and O(1) space with two rolling variables: 40 stairs is 38 additions. The naive recursion instead makes about 2^n calls — for n = 40 that is over a billion, most of them recomputes of the same values.

Where it goes wrong

Base cases: ways(1) = 1 and ways(2) = 2 (the two-step jump is one way, not two). Seeding the pair as 1 and 1 shifts every later answer down.
Naive recursion without memoization is exponential — a real judge times out around n = 40. The rolling pair is the same math without the blowup. And past n = 45 the count exceeds a 32-bit int: use long long.
ways(0) = 1 (stand still) is a valid convention too — but mixing conventions mid-code double-counts. Pick one and read your loop against it.

Next step

It is the same numbers in a different coat: Fibonacci asks for the identical recurrence. The 2D upgrade of build-a-table-from-neighbours is Minimum Path Sum.

Two things to remember

DP = last move + smaller answers; derive it from the final step.
Two rolling variables replace the whole array when the recurrence looks back only 1–2 steps.

🐞 This version fails — open it and try

Seeds the pair as 1 and 1 — every answer after n = 1 comes out one step too small

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 1, b = 1;   // bug: ways(2) should be 2
    if (n == 1) { cout << 1 << endl; return 0; }
    for (int k = 3; k <= n; k++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << endl;
    return 0;
}