1-D Dynamic Programming

LeetCode 70

LeetCode #70Difficulty: EasyNeetCode 150

LeetCode 70: Climbing Stairs

LeetCode

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

Problem Description

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:
Input: n = 3
Output: 3

Explanation: 1+1+1, 1+2, 2+1.

Constraints:
  • 1 <= n <= 45

Core Mental Model

To reach step n, your final jump was either from step n-1 (1 step) or step n-2 (2 steps). Thus: Ways(n) = Ways(n-1) + Ways(n-2). This is the Fibonacci sequence!

Formal Loop Invariant

Invariant: Ways to reach step i equals sum of ways to reach step i-1 and step i-2.

Key Architectural Takeaway:

When current state depends only on the previous 2 states, optimize space from O(N) to O(1) using two variables.

Asymptotic Complexity Analysis

Time ComplexityO(N)Linear scan
Space ComplexityO(1) constant scalars.Constant auxiliary

Bottleneck: Linear Fibonacci loop.

Edge Cases & Screener Traps

  • n = 1
  • n = 2