Code Logo

Minimum Cost to Reach the Top

Published at05 Jan 2026
Created by
Easy 0 views
Like16

This problem is about climbing past the end of a staircase while paying as little total cost as possible. Each position in costs tells you how much you pay when you land on that step, and from any step you can move forward by either 1 or 2 steps.

Because you can jump over steps, the cheapest path is not always the one that uses the fewest moves. Sometimes paying one medium cost lets you avoid two expensive landings later. So the goal is to minimize the full path cost, not just make a locally cheap move.

For example, if costs = [10,15,20], the answer is 15. Landing on the step with cost 15 and then moving past the end is cheaper than paths that include 10 and 20. If costs = [1,100,1,1,1,100,1,1,100,1], the answer is 6 because a good path lands mostly on the steps with cost 1.

So the task is to find the minimum total cost needed to move beyond the last index when each move can advance either 1 or 2 steps.

Example Input & Output

Example 1
Input
costs = [10, 15, 20]
Output
15
Explanation

Step on 15 and then move past the end.

Example 2
Input
costs = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output
6
Explanation

One low-cost path collects costs 1 + 1 + 1 + 1 + 1 + 1 = 6.

Example 3
Input
costs = [5]
Output
5
Explanation

Land on the only step and finish.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Cost to Reach the Top
Recommendation Algorithm Flow for Minimum Cost to Reach the Top

Solution Approach

A good fit here is dynamic programming. For each step, we compute the minimum cost needed to land on that step. Once we know that for earlier steps, the next answer becomes easy to build.

The key observation is that to land on step i, the previous move must have come from step i - 1 or step i - 2. That means the cheapest way to reach i is the cheaper of those two earlier paths, plus the current landing cost.

We can define it like this:

dp[i] = costs[i] + Math.min(dp[i - 1], dp[i - 2]);

That recurrence says: pay for the current step, then add the cheapest way to get close enough to land there.

The first two values are straightforward:

dp[0] = costs[0];
dp[1] = costs[1];

After that, we fill the array from left to right:

for (let i = 2; i < costs.length; i++) {
  dp[i] = costs[i] + Math.min(dp[i - 1], dp[i - 2]);
}

To move past the staircase, the final jump must come from either the last step or the second-to-last step, so the final answer is the cheaper of those two totals:

return Math.min(dp[costs.length - 1], dp[costs.length - 2]);

If there is only one step, the answer is just that single cost. Overall, this runs in O(n) time.

Best Answers

java
class Solution {
    public int min_cost_climbing_stairs(Object cost) {
        int[] arr = (int[]) cost;
        if (arr.length <= 1) {
            return arr.length == 0 ? 0 : arr[0];
        }
        int prev2 = arr[0];
        int prev1 = arr[1];
        for (int i = 2; i < arr.length; i++) {
            int curr = arr[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        return Math.min(prev1, prev2);
    }
}