0931MediumMathDynamic Programming

Cheapest Way to Break a Pile Down

Tracked in this browser only

Trains the technique from

LeetCode 3857Minimum Cost to Split into Ones

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A single pile holds n tokens.

One break takes a pile holding at least two tokens and divides it into two piles, each holding at least one token, at a cost equal to the size of the pile being broken. Breaks continue until every pile holds a single token.

Return the least total cost of getting there.

Examples

Example 1

Input: n = 7
Output: 20

Breaking the seven into three and four costs 7. The three then costs 5 and the four costs 8, coming to 20. Peeling single tokens off instead would cost 7 plus 6 plus 5 plus 4 plus 3 plus 2, which is 27.

Example 2

Input: n = 1
Output: 0

The pile already holds a single token, so nothing needs breaking.

Example 3

Input: n = 8
Output: 24

Halving all the way down costs 8, then two piles of four at 4 each, then four piles of two at 2 each, coming to 24.

Constraints

1 <= n <= 500

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_cost(n: int) -> int:

Java

public int minCost(int n)

The intended approach

Time O(n^2) for a pile of n tokens: each size tries every split.Space O(n) for the table of costs.

The cost of a break depends only on the size of the pile being broken, and the two piles it leaves are then broken down independently of each other, so the cheapest way to break a pile of a given size does not depend on where that pile came from. That makes the cost for each size settled once the smaller sizes are. A pile of one costs nothing. A pile of size `s` costs `s` for its own break plus the cheapest costs of the two pieces, so try every way of splitting `s` and keep the smallest total. Building the sizes upward fills the table in one sweep. It is worth knowing where that table ends up: splitting as evenly as possible always wins, because the pieces are broken down again and a lopsided piece goes on paying for its own size all the way down. So the table agrees, at every size, with simply halving and recursing, and the search over splits confirms that rather than discovering anything else.

Pythonentry point: min_cost

def min_cost(n):
    best = [0] * (n + 1)
    for size in range(2, n + 1):
        cheapest = None
        for left in range(1, size // 2 + 1):
            total = best[left] + best[size - left]
            if cheapest is None or total < cheapest:
                cheapest = total
        best[size] = size + cheapest
    return best[n]

The obvious version

Search over the piles themselves. A position is the collection of pile sizes currently on the table, and every break of every pile that can still be broken is tried, remembering the collections already settled. Explores the breaking rather than reasoning about one size at a time.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost(n):
    memo = {}

    def settle(piles):
        key = piles
        if key in memo:
            return memo[key]
        breakable = False
        for size in piles:
            if size >= 2:
                breakable = True
                break
        if not breakable:
            return 0
        best = None
        seen = set()
        for at in range(len(piles)):
            size = piles[at]
            if size < 2:
                continue
            for left in range(1, size):
                rest = list(piles[:at]) + list(piles[at + 1:]) + [left, size - left]
                rest.sort()
                nxt = tuple(rest)
                if nxt in seen:
                    continue
                seen.add(nxt)
                total = size + settle(nxt)
                if best is None or total < best:
                    best = total
        memo[key] = best
        return best

    if n == 1:
        return 0
    return settle((n,))

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in