Subscription Upgrade Min Cost
A SaaS product lets a user upgrade from any tier to any higher tier in one or more hops. Each hop has a fixed cost given by an array steps where steps[i] is the cost of moving from tier i to tier i+1 (i.e. one step up). The user starts at tier 0 and wants to reach tier n. Find the minimum total cost, given they may also do 'two-step' jumps that cost the same as steps[i] (treating the skip as one transaction).
Problem
Given an integer array steps of length n where steps[i] is the cost of moving from tier i to tier i+1, return the minimum total cost to reach tier n starting from tier 0. At each tier i (0 ≤ i ≤ n − 1), the user may EITHER take one step (paying steps[i] and landing at i+1) OR take a two-step jump (paying steps[i] and landing at i+2, if i+2 ≤ n).
Input
An integer n (1 ≤ n ≤ 10^5) and the array steps of length n (0 ≤ steps[i] ≤ 10^4).
Output
A single integer — the minimum total cost to reach tier n.
Constraints
- 1 ≤ n ≤ 100,000
- 0 ≤ steps[i] ≤ 10,000
- Starting tier is 0; goal tier is n
- At tier n - 1 only a single step is possible (no i+2 jump beyond n)
Examples
Example 1
Input
steps = [10, 15, 20]
Output
25
Tiers are 0,1,2,3. From tier 0 take the single step (steps[0]=10) to reach tier 1, then jump from tier 1 to tier 3 paying steps[1]=15. Total 10+15=25. Every other route costs more: all single steps = 10+15+20=45; jump 0→2 (10) then step 2→3 (20) = 30.
Example 2
Input
steps = [1]
Output
1
n=1, one step from tier 0 to tier 1.