Climbing Stairs
- 2 min read
- LC-Easy
- Dynamic Programming
3 years ago
Solution (Memoization)
- If we were to solve it normally, i.e. not use a memoized approach, the time complexity would be O(2^n) since there are two branches at each node.
- Once memoized, our TC comes down to O(n) since we only need to make a computation for a certain
ionce. After that initial time, we store it in our memo for later use. - Think of it like this: there are multiple ways to reach a certain stair. Once we reach that certain stair, the paths starting from that stair would be the same regardless of where we initially started from. That's the idea behind memoization.
dp[i]refers to how many ways are there to reach stepi, starting fromi?- If you're at the last step (i.e. the goal), there is exactly one way: DO NOTHING.
- You're already there, so
dp[i] = 1
- You're already there, so
- If you're at the last step (i.e. the goal), there is exactly one way: DO NOTHING.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) | Time is O(n) because for each i, only one computation is made. The rest comes from the memoized values |
def climbStairs(self, n: int) -> int:
memo = {}
def dfs(i):
if i > n:
return 0
if i == n:
return 1
if i not in memo:
memo[i] = dfs(i + 1) + dfs(i + 2)
return memo[i]
return dfs(0)
Solution (Dynamic Programming)
- Start from the back instead,
- We start from n = 5, see how much steps we can go from there, then go back to n = 4, etc.
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1) # n = 2, [0, 0, 0]
dp[n] = 1
dp[n - 1] = 1
for i in range(n - 2, -1, -1):
dp[i] = dp[i + 1] + dp[i + 2]
return dp[0]
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0 for _ in range(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]