Problem Explanation

In this problem, we have a staircase and each step of the stair comes with a certain cost to climb. Our purpose is to find the minimum cost to reach the top of the floor. We have two possible ways to start our climb: from the step with index 0 or the step with index 1. It should be noted that once we pay the cost for a step, we have the choice to climb one or two steps.

Let's walk through an example to illustrate it. Suppose that cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]. The cheapest way is to start on cost[0], and only step on 1s, skipping the cost[3] to reach the top. So, the minimum cost to reach the top of the floor would be 6.

Approach

The algorithm we use here to solve the problem is a simple form of dynamic programming. The main idea is to traverse the array from index 2, and for each index, we calculate the cost of reaching that step by adding the minimum cost of the two previous steps. We continue this process until we reach the last step where we return the minimum cost of the last two steps.

Let's take the example about cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]. The cost array before processing the steps is

1
2
31 -> 100 -> 1 -> 1 -> 1 -> 100 -> 1 -> 1 -> 100 -> 1

After processing the steps, the cost array becomes

1
2
31 -> 100 -> 2 -> 2 -> 3 -> 103 -> 4 -> 4 -> 104 -> 6

So the minimum cost to reach the top is 6.

Python Solution

1
2python
3class Solution:
4    def minCostClimbingStairs(self, cost):
5        n = len(cost)
6        for i in range(2, n):
7            cost[i] += min(cost[i - 1], cost[i - 2])
8        return min(cost[n - 1], cost[n - 2])

Java Solution

1
2java
3class Solution {
4    public int minCostClimbingStairs(int[] cost) {
5        int n = cost.length;
6        for(int i = 2; i < n; i++){
7            cost[i] += Math.min(cost[i-1], cost[i-2]);
8        }
9        return Math.min(cost[n - 1], cost[n - 2]);
10    }
11}

JavaScript Solution

1
2javascript
3class Solution {
4    minCostClimbingStairs(cost) {
5        let n = cost.length;
6        for(let i=2; i<n; i++){
7            cost[i] += Math.min(cost[i-1], cost[i-2]);
8        }
9        return Math.min(cost[n - 1], cost[n - 2]);
10    }
11}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int minCostClimbingStairs(vector<int>& cost) {
6        int n = cost.size();
7        for(int i=2; i<n; i++){
8            cost[i] += min(cost[i-1], cost[i-2]);
9        }
10        return min(cost[n - 1], cost[n - 2]);
11    }
12};

C# Solution

1
2csharp
3public class Solution {
4    public int MinCostClimbingStairs(int[] cost) {
5        int n = cost.Length;
6        for(int i=2; i < n; i++){
7            cost[i] += Math.Min(cost[i-1], cost[i-2]);
8        }
9        return Math.Min(cost[n - 1], cost[n - 2]);
10    }
11}

Note: In all these solutions, we are accumulating costs as we step through the array, updating each step with its minimum cost of getting to that point. When we reach the end, we return the last step which has the smallest cost. These solutions demonstrate the use of the dynamic programming technique in practice.# Ruby Solution

1
2ruby
3class Solution
4    def min_cost_climbing_stairs(cost)
5        n = cost.length
6        for i in 2...n
7            cost[i] += [cost[i - 1], cost[i - 2]].min
8        end
9        return [cost[n - 1], cost[n - 2]].min
10    end
11end

Swift Solution

1
2swift
3class Solution {
4    func minCostClimbingStairs(_ cost: [Int]) -> Int {
5        var cost = cost
6        let n = cost.count
7        for i in 2..<n {
8            cost[i] += min(cost[i - 1], cost[i - 2])
9        }
10        return min(cost[n-1],cost[n-2])
11    }
12}

R Solution

1
2r
3MinCostClimbingStairs <- function(cost) {
4    n <- length(cost)
5    for (i in 3:n) {
6        cost[i] <- cost[i] + min(cost[i - 1], cost[i - 2])
7    }
8    return (min(cost[n], cost[n - 1]))
9}

All these scripts in different languages effectively execute the same dynamic programming strategy - remember the minimum cost of reaching the two most recent steps, then when we're looking at a new step, its cost is its inherent cost plus the minimum cost of the two previous steps. This approach allows us to traverse the cost array in linear time, making it a very efficient strategy. It also takes constant space since only two values need to be stored and updated - the minimum cost to reach the two most recent steps.