TARGET DECK: Leetcode FILE TAGS:
Intuition
- In top down approach, it is the minimum of the previous and previous previous added to the current cost, and you must backtrack from the first and second steps separately, since you start from those.
- For bottom up, think of cases outside the problem to generalize for more difficult problems.
- In this case, we imagine two steps previous to the 1st and second step, which allows starting from an index 0 within the for loop.
Cards
START Basic Front: Min Cost Climbing Stairs - LeetCode Back: For top down, OPT[i] = cost[i] + min(OPT[i - 1], OPT[i - 2]), in which you start and end at bottom two 0 steps, and top 0 step.
END
Complexity
Runtime
with tabulation or memoization
Space
- with clobbering original cost array or bottom up with two variables.
- with memoization to store each subproblem.
Code
Bottom Up from Index 0
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
prev = nxt = 0
for i in range(len(cost)):
prev, nxt = nxt, cost[i] + min(prev, nxt)
return min(prev, nxt)Bottom Up from Index 2
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
prev, nxt = cost[0], cost[1]
for i in range(2, len(cost)):
prev, nxt = nxt, cost[i] + min(prev, nxt)
return min(prev, nxt)Top Down Clobbering Cost Array
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
if n == 2:
return min(cost[0], cost[1])
cost.append(0)
for i in range(2, n + 1):
cost[i] = cost[i] + min(cost[i - 1], cost[i - 2])
return cost[-1]