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 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
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
return self.climbStairs(n - 2) + self.climbStairs(n - 1)
Time Complexity: O(2^N)
Space Complexity: O(1)
class Solution:
def climbStairs(self, n: int) -> int:
# If n == 0 or 1
ansList = {
0 : 1,
1 : 1
}
for i in range(2, n + 1):
ansList[i] = ansList[i - 1] + ansList[i - 2]
return ansList[n]
Time Complexity: O(N)
Space Complexity: O(N)
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 1
for i in range(2, n + 1):
temp = two
two += one
one = temp
return two
Time Complexity: O(N)
Space Complexity: O(1)
https://leetcode.com/problems/climbing-stairs/discuss/2580551/100-Best-Solution-Explained
TODO
Time Complexity: O()
Space Complexity: O()