Climbing stairs
July 31, 2022
dynamic-programmingProblem URL: Climbing stairs
We will first solve it in recursive brute force, the use memoization to make it efficient. If the number of stairs is less than or equal to 1, then we can climb the stair with 1 step, this will be our base case. And we can take at most 2 steps, so we can either take 1 step or 2 step at a time, this will be our recursive call.
class Solution:
def climbStairs(self, n: int) -> int:
def _climbStairs(n: int, memo: dict) -> int:
if n in memo:
return memo[n]
if n <= 1:
return 1
memo[n] = _climbStairs(n-1, memo) + _climbStairs(n-2, memo)
return memo[n]
return _climbStairs(n, {})
Time Complexity: O(n)
Space Complexity: O(n)