leetcode-70 Climbing Stairs

[70] Climbing Stairs

Key Concept: Basic DP / Fibonacci Pattern - The number of ways to reach step n is the sum of ways to reach step n-1 (then take 1 step) and step n-2 (then take 2 steps). This is the Fibonacci sequence!

DP Foundation: This problem teaches the fundamental DP principle: optimal substructure and overlapping subproblems.

# 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?
#
# Example 1:
# Input: n = 2
# Output: 2
# Explanation: 1. 1 step + 1 step, 2. 2 steps
#
# Example 2:
# Input: n = 3
# Output: 3
# Explanation: 1. 1+1+1, 2. 1+2, 3. 2+1
#
# Constraints:
# 1 <= n <= 45

class Solution:
    # Approach 1: DP with O(n) space
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2

        for i in range(3, n + 1):
            # Ways to reach step i = ways to reach (i-1) + ways to reach (i-2)
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]

    # Approach 2: Space Optimized O(1)
    def climbStairs2(self, n: int) -> int:
        if n <= 2:
            return n

        # Only need previous two values
        prev2, prev1 = 1, 2

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

    # Approach 3: Recursive with Memoization
    def climbStairs3(self, n: int) -> int:
        memo = {}

        def dp(i):
            if i <= 2:
                return i
            if i in memo:
                return memo[i]

            memo[i] = dp(i - 1) + dp(i - 2)
            return memo[i]

        return dp(n)

# Time Complexity: O(n)
# Space: O(n) for array DP, O(1) for optimized version
#
# DP Recurrence: dp[i] = dp[i-1] + dp[i-2]
# This is the Fibonacci sequence starting with f(1)=1, f(2)=2