LC746. Min Cost Climbing Stairs

DP: DFS with Memoization

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        min_cost = sys.maxsize
        dp = {}
 
        def dfs(step):
            if step >= len(cost):
                return 0
 
            if step == len(cost) - 1:
                return cost[step]
            
            if step in dp:
                return dp[step]
 
            cost1 = cost[step] + dfs(step + 1)
            cost2 = cost[step] + dfs(step + 2)
 
            dp[step] = min(cost1, cost2)
            return dp[step]
        
        return min(dfs(0), dfs(1))

Complexity

Time: $O(n)$
Space: $O(n)$

DP: Bottom-up (Optimal)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
 
        for i in range(n - 3, -1, -1):
            cost1 = cost[i] + cost[i + 1]
            cost2 = cost[i] + cost[i + 2]
            cost[i] = min(cost1, cost2)
        
        return min(cost[0], cost[1])

Complexity

Time: $O(n)$
Space: $O(1)$