Min Cost Climbing Stairs — Fibonacci DP

Problem

Each cost[i] is paid to leave step i. You can start at step 0 or 1. Find minimum cost to reach top (beyond last step).

Approach

dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Answer = min(dp[n-1], dp[n-2]).

Space-optimize with two variables.

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

Solutions

Python

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a,b=cost[0],cost[1]
        for i in range(2,len(cost)):
            a,b=b,cost[i]+min(a,b)
        return min(a,b)

C++

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int a=cost[0],b=cost[1];
        for(int i=2;i<cost.size();i++){int c=cost[i]+min(a,b);a=b;b=c;}
        return min(a,b);
    }
};

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int a=cost[0],b=cost[1];
        for(int i=2;i<cost.length;i++){int c=cost[i]+Math.min(a,b);a=b;b=c;}
        return Math.min(a,b);
    }
}

Complexity

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