[LeetCode] 0070. climbing stairs

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Table of contents

Easy

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: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: n=3
Output: 3
Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

Constraints:

1 <= n <= 45

Python

				
					class Solution: # time complexity: O(n) # space complexity: O(n) # Cashe with brute force # def climbStairs(self, n: int) -> int: # memo = [0] * (n+1) # return self.climb_Stairs(0, n, memo) # time complexity: O(n) # space complexity: O(n) # def climb_Stairs(self, i: int, n: int, memo: list) -> int: # if (i > n): # return 0 # if (i == n): # return 1 # if (memo[i]): # return memo[i] # memo[i] = self.climb_Stairs(i+ 1 , n, memo) + \ # self.climb_Stairs(i+2, n, memo) # return memo[i] # time complexity: O(n) # space complexity: O(b) # Dynamic Programming # def climbStairs( self , n: int): # if n == 1: # return 1 # dp = [0] * (n + 1) # dp[1] = 1 # dp[2] = 2 # for i in range(3, n+1): # dp[i] = dp[i-1] + dp[i-2] # return dp[n] # time complexity: O(n) # space complexity: O(1) # Fibonacci Number def climbStairs(self, n: int) -> int: if n == 1: return 1 first = 1 second = 2 third = 0 for i in range(3, n+1): third = first + second first = second second = third return second n = 50 print(Solution().climbStairs(50))

Easy

Python

related articles