Show problems as
Classic problem #3010EasyArraySortingEnumeration

Divide an Array Into Subarrays With Minimum Cost I

Real-world version: Cutting the Conveyor Into Three Stretches
Tracked in this browser only
Read Divide an Array Into Subarrays With Minimum Cost I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A conveyor holds crates whose weights are weights. Cut it into exactly three stretches of neighbouring crates, each stretch holding at least one crate.

A stretch is charged the weight of its own first crate, and the total charge is the three added up.

Return the smallest total charge.

Examples

Example 1

Input
weights = [1, 2, 3, 4, 5]
Output
6

The first stretch has to begin at the first crate, so its 1 is unavoidable. The cheapest two crates left to begin stretches at are the 2 and the 3.

Example 2

Input
weights = [5, 4, 3, 2, 1]
Output
8

The 5 is forced. Beginning the other two stretches at the 1 and the 2 gives 8, and no other pair is cheaper.

Example 3

Input
weights = [1, 1, 1]
Output
3

Every crate weighs 1 and three stretches have to be charged.

Constraints

  • 3 <= weights.length <= 50
  • 1 <= weights[i] <= 50

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def minimum_cost(weights: list[int]) -> int:
Java
public int minimumCost(int[] weights)

More on the same topics