Solution: Min Cost Climbing Stairs

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #746 (Easy): Min Cost Climbing Stairs

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:

Example 1:
Input:	cost = [10,15,20]
Output:	15
Explanation:	Cheapest is: start on cost[1], pay that cost, and go to the top.

Example 2:
Input:	cost = [1,100,1,1,1,100,1,1,100,1]
Output:	6
Explanation:	Cheapest is: start on cost[0], and only step on 1s, skipping cost[3].

---

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This is an introduction to a top-down dynamic programming (DP) approach solution. We can think of this as the build-up of a number of smaller subproblems, starting at the end.

At each step, we can consider the answer to be the combined cost of the current step, plus the lesser result of the total cost of each of the solutions starting at the next two steps. This means that, thinking backwards, we can solve for the smallest problem first, and then build down from there.

For the last two steps, the answer is clearly their individual cost. For the third to last step, it's that step's cost, plus the lower of the last two steps. Now that we know that, we can store that data for later use at lower steps. Normally, this would call for a DP array, but in this case, we could simply store the values in-place.

(Note: If we choose to not modify the input, we could create a DP array to store this information at the expense of O(N) extra space.)

So we should iterate downward from the end, starting at the third step from the end, and update the values in cost[i] with the best total cost from cost[i] to the end. Then, once we reach the bottom of the steps, we can choose the best result of cost[0] and cost[1] and return our answer.

• Time Complexity: O(N) where N is the length of cost
• Space Complexity: O(1)
  • or O(N) if we use a separate DP array

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var minCostClimbingStairs = function(cost) {
    for (let i = cost.length - 3; ~i; i--)
        cost[i] += Math.min(cost[i+1], cost[i+2])
    return Math.min(cost[0], cost[1])
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

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

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        for (int i = cost.length - 3; i >= 0; i--)
            cost[i] += Math.min(cost[i+1], cost[i+2]);
        return Math.min(cost[0], cost[1]);
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

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

Comments

[dee-ksha]

thankyou, it was really helpful