Min Cost Climbing Stairs

Problem Description

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Examples

Constraints

• 2 ≤ cost.length ≤ 1000
• 0 ≤ cost[i] ≤ 999

State Transition and Space Optimization

Let dp[i] be the minimum cost to reach step i. To reach step i, we must have come from either step i - 1 or step i - 2. Thus: dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])

We want to reach the “top” of the floor, which is step n (one past the last element). The cost to step onto the top floor is 0, so the final answer is min(dp[n - 1], dp[n - 2]).

Since we only ever reference the last two computed states (dp[i - 1] and dp[i - 2]), we can optimize the space to O(1) by keeping just two variables, prev1 and prev2.

Solution: O(1) Space DP

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = cost[0];
        int prev1 = cost[1];

        for (int i = 2; i < n; i++) {
            int curr = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }

        return Math.min(prev1, prev2);
    }
}

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        prev2 = cost[0]
        prev1 = cost[1]

        for i in range(2, n):
            curr = cost[i] + min(prev1, prev2)
            prev2 = prev1
            prev1 = curr

        return min(prev1, prev2)

#include <vector>
#include <algorithm>

class Solution {
public:
    int minCostClimbingStairs(std::vector<int>& cost) {
        int n = cost.size();
        int prev2 = cost[0];
        int prev1 = cost[1];

        for (int i = 2; i < n; i++) {
            int curr = cost[i] + std::min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }

        return std::min(prev1, prev2);
    }
};

Complexity Analysis:

• Time Complexity: O(N) where N is the length of cost. We make one pass over the array.
• Space Complexity: O(1) auxiliary space.

← All Problems