Climbing Stairs

Easy

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

Python Solution

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

JavaScript Solution

function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

Step-by-Step Explanation

Same recurrence as Fibonacci: ways(n) = ways(n-1) + ways(n-2).
Use iterative DP with two variables to avoid recursion.

Complexity Analysis

Time	O(n)
Space	O(1)

All Problems

Two Sum Reverse a String Palindrome Check FizzBuzz Binary Search Reverse Linked List Merge Two Sorted Arrays Valid Parentheses Maximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted Array Nth Fibonacci Number Valid Anagram First Unique Character Roman to Integer Best Time to Buy and Sell Stock Contains Duplicate Move Zeroes Intersection of Two Arrays Longest Common Prefix

Climbing Stairs

Examples

Python Solution

JavaScript Solution

Step-by-Step Explanation

Complexity Analysis

Tags

Related Problems

All Problems