Solve the climbing stairs problem from leetcode in Python
- User
Solve the climbing stairs problem from leetcode in Python
Assistant
The "Climbing Stairs" problem on LeetCode asks to find the number of ways to climb a staircase with n steps, given that you can either climb 1 or 2 steps at a time.
Here's the Python implementation:
class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n first = 1 second = 2 for I in range(3, n+1): next = first + second first = second second = next return secondThe algorithm works by keeping track of the number of ways to climb the first two steps (
firstandsecond). For each subsequent step, we calculate the number of ways to climb that step by adding the number of ways to climb the previous step either with one step (first) or two steps (second). We updatefirstandsecondwith the new value and repeat the process until we reach the last step. The final value ofsecondis the number of ways to climb the entire staircase.Time complexity: O(n) Space complexity: O(1)
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.