LeetCode 70 Climbing Stairs - Example and Complexity Analysis

Trace n = 5.

dp[1] = 1 (one way: single step) dp[2] = 2 (two ways: 1+1 or 2) dp[3] = dp[2] + dp[1] = 2 + 1 = 3 dp[4] = dp[3] + dp[2] = 3 + 2 = 5 dp[5] = dp[4] + dp[3] = 5 + 3 = 8

Answer: $8$ ways to climb $5$ stairs.

Verify: 11111, 1112, 1121, 1211, 2111, 122, 212, 221. That's $8$.

$O(n)$ time iterating once. $O(1)$ space keeping only two previous values.