Climbing Stairs — Blind 75 practice

Problem

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Examples

Example 1:
Input: n = 2
Output: 2

Example 2:
Input: n = 3
Output: 3

Example 3:
Input: n = 5
Output: 8

Constraints

1 <= n <= 45

Prerequisites

Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence.
Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.

How to think about it

1. Fibonacci in Disguise Optimal

Intuition

The last move onto step n was either a single step from n-1 or a double from n-2, and those two sets of routes share nothing — so the count is their sum. That is the Fibonacci recurrence, and recognising it is the whole problem. Two rolling variables replace the table, because a step never looks further back than two.

Algorithm

1. One step: one way. Two steps: two ways.
2. Walk upward keeping the counts for the previous two steps.
3. Each step's count is their sum.

Time & Space

Time O(n). Space O(1) with rolling variables; the naive recursion is exponential without memoisation, which is worth saying.