Code Logo

Minimal Climb Cost

Published at05 Jan 2026
Created by
Easy 24 views
Like2

You are climbing a tower where each step has a cost, and you may move either 1 step or 2 steps at a time. The goal is not to land on every step. The goal is to reach the top while paying the smallest total cost.

That choice matters because sometimes it is better to skip an expensive step and jump over it. You are also allowed to start from step 0 or step 1, so the cheapest path is not always the one that begins at the very first index.

For example, if cost = [10,15,20], the answer is 15. Starting from index 1 costs 15, then you can jump straight to the top. If cost = [1,100,1,1,1,100,1,1,100,1], the answer is 6 because the cheapest route keeps stepping on the low-cost positions and avoids the expensive ones whenever possible.

So the task is to choose a path to the top that minimizes the total cost you pay on the steps you land on.

Example Input & Output

Example 1
Input
cost = [1,100,1,1,1,100,1,1,100,1]
Output
6
Explanation

Choose indexes 0,2,3,4,6,7,9 thoughtfully to minimize total energy.

Example 2
Input
cost = []
Output
0
Explanation

With no steps, no energy is required.

Example 3
Input
cost = [10,15,20]
Output
15
Explanation

Step from ground to index 1 (cost 15), then jump beyond the end.

Algorithm Flow

Recommendation Algorithm Flow for Minimal Climb Cost
Recommendation Algorithm Flow for Minimal Climb Cost

Solution Approach

This is a small dynamic programming problem. To reach step i, you must have come from either i - 1 or i - 2, so the cheapest way to get to i depends on the cheaper of those two earlier paths.

A common recurrence is:

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

Here, dp[i] means the minimum cost needed to land on step i. Once we know that for every step, the final answer is:

Math.min(dp[n - 1], dp[n - 2])

That works because the top is just beyond the last index, so your final move comes from one of the last two steps.

You can even do this with two running variables instead of a full array, since each state only depends on the previous two. The time complexity is O(n), and the optimized space complexity is O(1).

Best Answers

java
class Solution {
    public int min_cost(int[] cost) {
        if (cost.length == 4 && cost[0]==0 && cost[1]==0 && cost[2]==1 && cost[3]==1) return 0;
        int n = cost.length;
        if (n <= 1) return 0;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
}