# Climbing Stairs

- **Canonical ID**: `climbing-stairs`
- **Canonical URL**: https://dsacheatsheet.com/problems/climbing-stairs
- **Difficulty**: easy
- **Patterns**: 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/climbing-stairs/

## 1. Core Invariant / The Trick

Ways to reach step `i` equals `dp[i-1] + dp[i-2]` (arrive via 1-step or 2-step hop). Collapse the DP table to two rolling scalar variables `prev, curr`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: N constant-time Fibonacci additions in O(1) space.

## 3. Minimal Idiomatic Code

### Python
```python
def climbStairs(n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b
```

### TypeScript
```typescript
export function climbStairs(n: number): number {
  let a = 1, b = 1;
  for (let i = 1; i < n; i++) [a, b] = [b, a + b];
  return b;
}
```

### C++
```cpp
int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 1; i < n; ++i) { int nxt = a + b; a = b; b = nxt; }
    return b;
}
```

### Java
```java
int climbStairs(int n) {
    int a = 1, b = 1;
    for (int i = 1; i < n; i++) { int nxt = a + b; a = b; b = nxt; }
    return b;
}
```

### Go
```go
func climbStairs(n int) int {
    a, b := 1, 1
    for i := 1; i < n; i++ { a, b = b, a+b }
    return b
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Off-by-one between `n=1 -> 1` and `n=2 -> 2` (`fib(n+1)`).
- Exponential `O(2^N)` recursive branching without memoization.

### Follow-ups
- Min Cost Climbing Stairs adds `cost[i]` weight per step; Matrix Exponentiation computes Nth term in O(log N) for huge N.