Minimum Cost to Cut a Board into Squares

Minimum Cost to Cut a Board into Squares is a classic greedy problem. You are given a board and the cost of every possible horizontal and vertical cut, and you must slice it all the way down to unit squares for the least total money. The twist that makes it interesting: the price of a cut depends on how many pieces already exist on the other axis.

The slow way first

You might think the order of cuts does not matter — but it does. Every cut's price is multiplied by the number of pieces on the other axis, and that count only grows as you cut. So a cut you delay gets more expensive. Trying every possible ordering of the cuts is factorial time — hopelessly slow even for a small board.

The question to ask: which cut should I always make first to keep multipliers small?

The idea: spend the big cuts while multipliers are tiny

Make the most expensive cut as early as possible, while the perpendicular piece count is still low. Concretely: sort both cost lists descending, then repeatedly compare the two current heads and take the larger one. Its cost is multiplied by the current piece count on the opposite axis, and making that cut bumps the piece count on its own axis by one.

Why greedy is correct: every cut will eventually be multiplied by some piece count, and those counts only increase. Paying for the priciest cuts while the multiplier is smallest, and the cheap cuts last when the multiplier is largest, minimizes the weighted sum — a standard exchange-argument result.

Walk through it

Step through the animation. H = [4, 1] and V = [3, 2] are sorted descending. We compare heads 4 vs 3 and take 4 (× v_pieces 1). Then 3 beats 1, taken × h_pieces 2. Then 2 beats 1, taken × h_pieces 2. Finally only 1 remains, taken × v_pieces 3. The running cost climbs 4 → 10 → 14 → 17.

Pseudocode

sort h descending, sort v descending
h_pieces = v_pieces = 1
cost = 0
while both lists still have cuts:
    if head of h >= head of v:
        cost += h_head * v_pieces   # horizontal cut crosses every vertical piece
        h_pieces += 1               # one more horizontal piece exists now
        drop h_head
    else:
        cost += v_head * h_pieces
        v_pieces += 1
        drop v_head
drain whatever list is left, multiplying by the other axis count
return cost

The Python solution

def min_cost(h_cost, v_cost):
    h = sorted(h_cost, reverse=True)
    v = sorted(v_cost, reverse=True)
    i = j = 0
    h_pieces = v_pieces = 1
    cost = 0
    while i < len(h) and j < len(v):
        if h[i] >= v[j]:
            cost += h[i] * v_pieces; h_pieces += 1; i += 1
        else:
            cost += v[j] * h_pieces; v_pieces += 1; j += 1
    while i < len(h): cost += h[i] * v_pieces; h_pieces += 1; i += 1
    while j < len(v): cost += v[j] * h_pieces; v_pieces += 1; j += 1
    return cost

• We sort both lists descending so the heads are always the costliest remaining cuts.
• h_pieces and v_pieces start at 1 — an uncut board is one piece on each axis.
• The main while loop runs until one list empties: each turn we take the larger head.
• A horizontal cut multiplies by v_pieces (it crosses every vertical piece) and then increments h_pieces.
• The two trailing while loops drain whatever cuts are left once the other list is empty.

Complexity

The cost is dominated by sorting the two lists; the merge that follows is linear. We trade a factorial search for two sorts and a single pass.

When this pattern shows up

Practice