Show problems as
Classic problem #1000HardArrayDynamic ProgrammingPrefix Sum

Minimum Cost to Merge Stones

Real-world version: Combining Grain Lots
Tracked in this browser only
Read Minimum Cost to Merge Stones on LeetCode(opens in a new tab)

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

A conveyor holds a row of grain lots, and weights[i] is the weight of the lot in position i.

One combine takes exactly groupSize lots that are neighbours in the current row and replaces them with a single lot whose weight is their combined weight. The handling charge for that combine is the combined weight of the lots it took. Combines may be repeated, and each one works on the row as it stands at that moment.

Return the smallest total handling charge that leaves the conveyor holding one lot. If no sequence of combines can leave exactly one lot, return -1.

Examples

Example 1

Input
weights = [8, 3, 5], groupSize = 2
Output
24

Combine the lots of weight 3 and 5 for a charge of 8, leaving lots of weight 8 and 8, then combine those for a charge of 16. The charges add up to 24.

Example 2

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

A combine turns three lots into one, so the row of four can only become a row of two, and a row of two admits no further combine. One lot is unreachable.

Example 3

Input
weights = [2, 9, 1, 8, 3], groupSize = 3
Output
35

Combine the lots of weight 1, 8 and 3 for a charge of 12, leaving weights 2, 9 and 12, then combine all three for a charge of 23. The charges add up to 35.

Constraints

  • 1 <= weights.length <= 30
  • 1 <= weights[i] <= 100
  • 2 <= groupSize <= 30

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 merge_lots(weights: list[int], groupSize: int) -> int:
Java
public int mergeLots(int[] weights, int groupSize)

More on the same topics