Problem #70: Climbing Stairs

Intuition & Strategy Breakdown

Use dynamic programming (similar to Fibonacci). dp[i] = dp[i-1] + dp[i-2], representing taking 1 step from (i-1) or 2 steps from (i-2).

Python Solution

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        # one = f(i-2), two = f(i-1)
        one, two = 1, 2
        
        for i in range(3, n + 1):
            temp = one + two
            one = two
            two = temp
            
        return two

Java Solution

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int one = 1;
        int two = 2;
        
        for (int i = 3; i <= n; i++) {
            int temp = one + two;
            one = two;
            two = temp;
        }
        
        return two;
    }
}