To solve the classic Climbing Stairs problem (LeetCode 70), where you can climb 1 or 2 steps at a time, here's an efficient Python solution:

Problem Statement (Assumed)

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

Approach

This problem is a classic example of dynamic programming. The key insight is:

• The number of ways to reach step i = ways to reach step i-1 (take 1 step up) + ways to reach step i-2 (take 2 steps up).
• Base cases:
  • n=1: Only 1 way (take 1 step).
  • n=2: 2 ways (1+1 or 2 steps).

We optimize space by using two variables to track the previous two steps instead of an array.

Solution Code

def climbStairs(n: int) -> int:
    if n == 1:
        return 1
    a, b = 1, 2  # a = ways to reach n-2, b = ways to reach n-1
    for _ in range(3, n+1):
        a, b = b, a + b  # Update to next steps
    return b

Explanation

• Initialization: a (ways to reach step 1) =1, b (ways to reach step2)=2.
• Iteration: For each step from 3 to n, compute the current ways as sum of previous two values. Update a and b to shift forward ( a becomes b, b becomes current value).
• Result: b holds the number of ways to reach step n.

Example Tests

• n=2 → 2 (1+1 or 2 steps).
• n=3 →3 (1+1+1,1+2,2+1).
• n=5 →8 (all combinations of 1 and 2 steps).

This solution runs in O(n) time and O(1) space, making it optimal for the given constraints (1 ≤ n ≤ 45). If the problem had different step options (e.g., 1,3,5 steps), the approach would adjust to sum the ways from those previous steps. Let me know if you need a solution for a different variation!

作者声明:本文包含人工智能生成内容。