Marathon Supply Crate Budget

Minimum cost to cover an array using given single and adjacent-pair costs

EasyDynamic ProgrammingPrefix DPMinimum Cost

A marathon has supply stations arranged in route order. Every station must receive supplies exactly once.

The organizer can purchase either of these packages:

  • A single-station crate for station i, costing solo[i].
  • A two-station crate for stations i and i + 1, costing paired[i].

A two-station crate supplies both stations completely. Purchased crates cannot overlap, and no station may be left uncovered. There are no other package types.

Return the minimum total cost of supplying all stations. If there are no stations, return 0.

Examples

Example 1

Input: solo = [8,5,9], paired = [10,7]
Output: 15

Buy a single-station crate for the first station and a two-station crate for the remaining two stations. This is cheaper than any other complete covering.

Example 2

Input: solo = [6,6,6,6], paired = [5,20,5]
Output: 10

Buy two-station crates for stations 0–1 and 2–3. The expensive crate for the middle pair is unnecessary.

Example 3

Input: solo = [], paired = []
Output: 0

There are no stations, so no crates are needed.

Constraints

  • 0 <= solo.length <= 6000
  • paired.length == max(0, solo.length - 1)
  • 0 <= solo[i] <= 1000000
  • 0 <= paired[i] <= 1000000
  • Stations are indexed from 0 in route order.

The answer is a minimum cost, not a list of crates. Multiple optimal purchases therefore do not create output ambiguity. The intended solution takes O(n) time and O(1) auxiliary space.

Hints

Show hint 1

Let dp[k] be the cheapest way to supply the first k stations.

Show hint 2

The last crate in a covering supplies either the last station alone or the last two stations together.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • Can you compute the minimum cost using constant auxiliary space?
  • How would you also return an optimal list of purchased crates, preferring fewer crates when total costs tie?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem