BudiBadu Logo

Minimum Cost to Reach the Top

Array Easy 0 views
Like16

You’re at the bottom of a staircase where every step has a positive price tag. In Minimum Cost to Reach the Top, your goal is to advance beyond the final step while paying as little as possible. You can climb either 1 or 2 steps at a time, but whenever you land on a step, you must pay the cost shown at that position.

The "secret sauce" here is Dynamic Programming (DP). Instead of guessing the path, you calculate the minimum cost to reach each step $i$ as cost[i] + min(total[i-1], total[i-2]). By building this result from the bottom up, you can find the single least-expensive path to the summit. You don't pay for the starting ground or the space beyond the last step—only for the steps you actually touch. This approach ensures you never overpay for your climb, even when weave-friendly low-cost paths are hidden among the more expensive steps!

When the task involves connectivity or route cost, build adjacency carefully and guard against revisiting stale states. Use a visited or best-distance structure to avoid repeated work, and ensure unreachable scenarios return the required fallback value instead of partial traversal results.

Examples

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 - Budibadu
Recommendation Algorithm Flow for Minimum Cost to Reach the Top - Budibadu

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);
    }
}