Staircase

The number of ways to reach step n is the sum of the ways to reach each step you could have jumped from — ways(n) = ways(n-1) + ways(n-2) + ways(n-3) — because every path to step n ends with exactly one last jump of size 1, 2, or 3, and those three cases partition all paths with no overlap.

Recognize the pattern

• Question asks to count the number of distinct ways to reach a target (not the min/max cost, not whether it's reachable).
• State at step i depends only on a fixed, small window of previous states (here: i-1, i-2, i-3).
• Moves are independent choices at each position with combinable outcomes — this signals a sum-of-subproblems recurrence, i.e. 1-D DP, not a single greedy choice.
• This tribonacci-style variant (steps of 1, 2, or 3) doesn't map to a single canonical LeetCode problem with a fixed published bound — don't borrow the n ≤ 45 constraint from the related but different 1/2-step "Climbing Stairs" problem (LeetCode 70, Fibonacci recurrence). Whatever bound your actual problem states, treat it as the tell for brute force vs. DP, and pick your integer type from the bound, not from a memorized number.

Brute force → optimal

Brute force: recursion directly on the recurrence, branching 3 ways at each step with no memory of repeated subproblems.

long waysBrute(int n) {
    if (n == 0) return 1;
    if (n < 0) return 0;
    return waysBrute(n-1) + waysBrute(n-2) + waysBrute(n-3);
}

Cost: exponential — same sub-value of n (e.g. waysBrute(5)) gets recomputed from scratch every time it's reached via a different jump sequence. Space: O(n) recursion stack only, but time is the killer.

Optimal: since ways(k) only ever needs to be computed once, cache it (top-down memo) or fill it bottom-up in a small array, then compress to three rolling variables. Note the return/array type is long, not int — see Pitfalls below for why.

long waysDP(int n) {
    if (n == 0) return 1;
    long[] dp = new long[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = (i - 1 >= 0 ? dp[i-1] : 0)
              + (i - 2 >= 0 ? dp[i-2] : 0)
              + (i - 3 >= 0 ? dp[i-3] : 0);
    }
    return dp[n];
}

// O(1) space, rolling window of the last 3 values
long waysDPOptimal(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    long a = 1, b = 1, c = 2; // ways(0), ways(1), ways(2)
    for (int i = 3; i <= n; i++) {
        long next = a + b + c;
        a = b; b = c; c = next;
    }
    return c;
}

Complexity, derived

Time: the array/rolling loop runs the body exactly once per step from 1 to n, each iteration doing a fixed number (3) of additions — total work = 3·n = O(n). The brute-force recursion instead forms a call tree where each node branches into 3 children down to depth ~n; that tree has on the order of 3ⁿ leaves in the worst decomposition, so brute force is bounded above by O(3ⁿ) time. A tighter bound comes from the characteristic equation of the recurrence, x³ = x² + x + 1; its dominant real root (the "tribonacci constant") is close to 1.839, giving Θ(1.839ⁿ) — we quote this figure rather than derive the root here, but either bound is exponential, which is the point: brute force is unusable well before n reaches the double digits.

Space: array version O(n) for the dp table; rolling version O(1) since only the last 3 values are ever needed — dp[i] never depends on anything before i-3.

Traced example: n = 4

Matches the problem's own example: n=3 → 4 ways, n=4 → 7 ways.

Pitfalls

• Wrong base cases: forgetting dp[0]=1 (one way to be at the ground: take zero steps) breaks the whole chain, since dp[1], dp[2], dp[3] all fold it in.
• Negative index access: for small n (n=1 or n=2) naively indexing dp[i-3] before guarding underflows the array — always bounds-check or special-case n < 3.
• Overflow — check this concretely, don't assume: counts grow roughly like 1.839ⁿ, and they grow fast. Computing this exact recurrence directly gives dp[45] = 501,774,317,241 (~5×10¹¹) — that already overflows a 32-bit int (max ~2.147×10⁹) by more than 200×. In fact the values exceed int range well before n=45 (dp[i] crosses ~2.1×10⁹ somewhere in the mid-to-high 30s for this recurrence). Never assume a bound like "n ≤ 45" is safe for int just because it sounds small — compute or bound the actual output magnitude for your specific recurrence and pick long (or a modulus, if the problem asks for one) accordingly. That's why the code above uses long throughout rather than int.
• Confusing this with the minimum jumps or reachability variant of stairs problems — those need min/OR instead of sum, a completely different recurrence.

When to use / when not — trade-offs

Use bottom-up rolling DP whenever the recurrence window is small and fixed (here, 3) — it gives O(n) time, O(1) space, and is trivial to prove correct by induction.

vs. plain recursion (no memo): simpler to write but exponential; only acceptable for tiny n or as a first correctness check before optimizing.

vs. matrix exponentiation: the recurrence is linear, so it can be expressed as a 3×3 matrix power, giving O(log n) time — worth it only if n is huge (e.g. 10⁹) and per-query speed matters; overkill and harder to get right for modest n, and you'd need modular arithmetic anyway since raw counts blow past 64-bit range for large n.

vs. memoized top-down recursion: equivalent time/space to bottom-up but pays recursion-call overhead and risks stack depth issues for large n; bottom-up is preferred once the recurrence direction is obvious.

Takeaways

• Counting problems with a fixed-size dependency window reduce to summing a constant number of prior states — always identify that window size first.
• Space can almost always be compressed from O(n) to O(window size) once you know dp[i] never looks further back than the window.
• Get the base cases exactly right before trusting the loop; they are the seed for every later value.
• Never trust a remembered constraint (like "n ≤ 45 fits in int") without checking it against the actual recurrence — a superficially similar problem can have a very different growth rate, and "fits in 32 bits" is a claim you should verify by computing the boundary value, not assert from memory.

Recall: If you could take 1, 2, 3, or 4 steps at a time, what does the recurrence for dp[i] become, and what are the new base cases needed?

Derived from the classic staircase / tribonacci-style counting problem; recurrence and complexity analysis are original to this page. The dp[45] value (501,774,317,241) was verified by direct computation of this exact recurrence.