mediumDynamic Programming 1DPure DSA~22 min
Deploy Stage Min Cost
A deploy pipeline is a ladder of stages, each with a flake-retry cost. From a stage you may advance one or two stages at a time. You may start at stage 0 or stage 1, and you finish once you step past the last stage. Minimise total cost.
Problem
Given an array cost where cost[i] is the cost of stepping on stage i, you may climb one or two stages per move and start from index 0 or 1. Return the minimum cost to climb past the top (reaching index n).
Input
An array cost of length n (2 ≤ n ≤ 10^5), values in [0, 999].
Output
A single integer — the minimum total cost to reach the top.
Constraints
- 2 ≤ n ≤ 100,000
- You may begin at index 0 or 1
- The goal index is n (past the last stage)
Examples
Example 1
Input
cost = [10, 15, 20]
Output
15
Start at index 1 (cost 15), then step two to reach the top.
Example 2
Input
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output
6
Hop across the cheap stages, skipping the two 100-cost stages.