Min Cost Climbing Stairs
- 2 min read
- LC-Easy
- Dynamic Programming
3 years ago
Solution (Memoization)
At any point in the dfs (EXCEPT THE FIRST STEP), you add the cost of the current step, and then go to next immediate step, or skip one and go 2 steps ahead. Don't get confused about the fact that you can start at index 0 or 1. This is irrelevant to the actual recursive function. You only account for this during the function call- i.e. taking the minimum of dfs(0) and dfs(1). Within DFS itself, you always take into account the cost of the current stair, and either move 1 or 2 steps forward.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) | |
def minCostClimbingStairs(self, cost: List[int]) -> int:
memo = {}
def dfs(i):
if i >= len(cost):
return 0
if i not in memo:
memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
return memo[i]
return min(dfs(0), dfs(1))
Solution (Dynamic Programming)
Since we have to add the cost of the current floor before traversing next options, we can use the input array itself, this basically takes our time to O(n) and space to O(1). Super cool!!
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])