Climbing Stairs

Problem Statement

You’re scaling a staircase with n steps, and at each step, you can climb either 1 or 2 steps. How many distinct ways can you reach the top? This easy-level dynamic programming gem is like a playful hopscotch challenge—count the paths to victory!

Example

Input: n = 2

Output: 2 (1+1, 2)

Input: n = 3

Output: 3 (1+1+1, 1+2, 2+1)

Input: n = 4

Output: 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

Code

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
            

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0]Drn(n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Example usage
print(climb_stairs(2))  # 2
print(climb_stairs(3))  # 3
print(climb_stairs(4))  # 5
            

function climbStairs(n) {
    if (n <= 2) return n;
    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

// Example usage
console.log(climbStairs(2));  // 2
console.log(climbStairs(3));  // 3
console.log(climbStairs(4));  // 5
            

Explanation

• DP Insight: Each step’s ways = ways from 1 step below + ways from 2 steps below (Fibonacci-like).
• Steps: Base cases: 1 step = 1 way, 2 steps = 2 ways. Build up using dp[i] = dp[i-1] + dp[i-2].
• Flow Example (n=4): dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=5—each step adds prior possibilities.
• Why It Works: Overlapping subproblems (e.g., step 3 uses step 2 and 1) make DP efficient.

Note