Show problems as
Classic problem #1547HardArrayDynamic ProgrammingSorting

Minimum Cost to Cut a Stick

Real-world version: Fabric Bolt Cutting Charges
Tracked in this browser only
Read Minimum Cost to Cut a Stick on LeetCode(opens in a new tab)

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

A mill receives a bolt of cloth length centimetres long and has to divide it at every mark in marks. A mark is written as its distance in centimetres from the left end of the bolt, so every mark sits strictly inside the cloth.

Cutting is done one pass at a time. A pass takes a single piece of cloth, feeds it through the blade at one of the marks still lying inside that piece, and hands back the two pieces either side of it. The mill bills a pass at the width of the piece that went in, no matter where within it the mark sat, and the bill for the job is the sum over all passes.

The passes may be made in any order you like, and the order matters, because a piece already divided is narrower for later passes.

Return the smallest total bill for dividing the bolt at every mark.

Examples

Example 1

Input
length = 7, marks = [5, 1, 4, 3]
Output
16

Passing at 3 bills 7 and leaves pieces 0-3 and 3-7; passing at 1 bills 3, at 5 bills 4, and at 4 bills 2, for 7 + 3 + 4 + 2 = 16.

Example 2

Input
length = 12, marks = [8]
Output
12

There is a single mark and a single pass, and the piece fed in is the whole bolt.

Example 3

Input
length = 20, marks = [2, 19]
Output
38

Passing at 2 bills 20 and passing at 19 then bills 18, for a total of 38.

Constraints

  • 2 <= length <= 10^6
  • 1 <= marks.length <= min(length - 1, 100)
  • 1 <= marks[i] <= length - 1
  • All values in marks are distinct.

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 min_cutting_charge(length: int, marks: list[int]) -> int:
Java
public int minCuttingCharge(int length, int[] marks)

More on the same topics