746. Min Cost Climbing Stairs

Description

The problem is to determine the minimum cost to reach the top of a staircase. You are given an array where each element represents the cost of stepping on that particular step. You can start at either step 0 or step 1, and you need to reach the top by stepping on one or two steps at a time.

Intuition

The key insight is that to minimize the total cost, at each step, you should choose the previous step that would have given you the minimum cost to reach it. This means you need to consider the cost of the previous step and the step before it to decide the minimum cost at the current step.

Approach

This problem can be solved using dynamic programming. We maintain a dp array where dp[i] represents the minimum cost to reach step i. The recurrence relation is: \[ \text{dp}[i] = \min(\text{dp}[i-1] + \text{cost}[i-1], \text{dp}[i-2] + \text{cost}[i-2]) \] We initialize dp[0] and dp[1] to 0, since the cost to start at either step is 0. Then, we iteratively compute the minimum cost for each subsequent step using the formula above.

Complexity

Time Complexity:

(O(n)), where (n) is the number of steps. We only need to iterate through the list of steps once.

Space Complexity:

(O(1)), because we only use a constant amount of extra space to store the dp values.

Code

C++

class Solution {
public:
    int minCostClimbingStairs(vector& cost) {
        vector dp(3, 0);
        for (int j = 2; j <= cost.size(); ++j) {
            dp[j % 3] = min(dp[(j - 1) % 3] + cost[j - 1], dp[(j - 2) % 3] + cost[j - 2]);
        }
        return dp[cost.size() % 3];
    }
};

Python

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

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[3];
        for (int j = 2; j <= cost.length; j++) {
            dp[j % 3] = Math.min(dp[(j - 1) % 3] + cost[j - 1], dp[(j - 2) % 3] + cost[j - 2]);
        }
        return dp[cost.length % 3];
    }
}

JavaScript

var minCostClimbingStairs = function(cost) {
    var dp = [0, 0];
    for(let j = 2; j <= cost.length; j++) {
        dp[j % 3] = Math.min(dp[(j - 1) % 3] + cost[j - 1], dp[(j - 2) % 3] + cost[j - 2]);
    }
    return dp.at(cost.length % 3);
};