Staircase Climbing Combinations

Implement staircaseClimbingCombinations(n) — count the number of distinct ways to climb a staircase of n steps when each move takes either 1 step or 2 steps. This is the classic Climbing Stairs problem. The answer follows the Fibonacci recurrence: the last move that lands you on the top was either a 1-step from step n-1 or a 2-step from step n-2, so ways(n) = ways(n-1) + ways(n-2).

Signature

// n: number  — the height of the staircase, a non-negative integer.
// returns: number
//   The count of distinct ordered sequences of 1-steps and 2-steps
//   that sum to exactly n.
function staircaseClimbingCombinations(n): number;

Examples

// Two steps: [1,1] or [2].
staircaseClimbingCombinations(2);
// → 2

// Five steps. The eight orderings include [1,1,1,1,1], [2,1,1,1],
// [1,2,1,1], ..., [2,2,1], [1,2,2], [2,1,2].
staircaseClimbingCombinations(5);
// → 8

Notes

• Order matters. [1, 2] and [2, 1] are two different ways to climb 3 steps — you count ordered sequences, not unordered groupings.
• ways(0) is defined as 1. There is exactly one way to climb a staircase of height 0: take no steps, because you are already at the top. This base case is what makes the recurrence line up with the Fibonacci numbers.
• ways(1) is 1. A single step has only one route: one 1-step.
• The sequence is Fibonacci-shifted. ways(n) equals the (n+1)-th Fibonacci number. Consecutive values satisfy ways(n) = ways(n-1) + ways(n-2).
• Aim for one pass. A direct recursion recomputes the same subproblems and is exponential. Two rolling variables give you O(n) time and O(1) space.