Leetcode 0746. Min Cost Climbing Stairs

Problem statement

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

Solution

We can use dp, where we keep only information about two last steps, namely dp1 and dp2 are the minimum costs to reach step before current step and step which is two steps before current step. To update values, we need to update in the same moment two values:

1. dp1 = dp2.
2. dp2 = cost[i] + min(dp1, dp2): we can reach it it two ways and we choose the minimum one.

It is very similar to problem 198 House Robber.

Complexity

Time complexity is O(n), space complexity is O(1).

Code

class Solution:
    def minCostClimbingStairs(self, cost):
        dp1, dp2 = 0, 0
        for i in range(len(cost)):
            dp1, dp2 = dp2, cost[i] + min(dp1, dp2)
            
        return min(dp1, dp2)