Leetcode # 746. Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

Solution

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

※ 參考 Leet Code #198. House Robber 

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

Last Updated on 2023/08/16 by A1go