560. Where to Put the Mailboxes

Houses stand at given positions along a street. Place exactly k mailboxes anywhere on the street. Each house walks to its nearest mailbox. Print the smallest possible total walking distance.

houses 1 4 8 10 20, k = 3 -> 5 houses 2 3 5 12 18, k = 2 -> 9

## Each mailbox serves a contiguous block

Sort the houses. Then the houses served by one mailbox form a CONTIGUOUS run.

The reason: if house a and house c both use mailbox M and some house b between them uses a different mailbox N, then N lies on one side of b, so it is at least as close to whichever of a or c is on that side as M is. Reassigning that house to N never increases the total, and repeating makes every assignment contiguous.

So the problem is a PARTITION of the sorted houses into k consecutive blocks, which is what makes an interval-flavoured DP apply. Without sorting there is no such structure, so the sort is part of the algorithm and not a convenience.

## The cost of one block is at the median

For a fixed block, the best mailbox position is a MEDIAN of that block, and the cost is the sum of distances to it.

The reason is worth knowing: moving the mailbox one step right changes the total by (number of houses to the left) - (number of houses to the right), so the total decreases while more houses lie to the right and increases after. The turning point is the median.

For an even-sized block, any position between the two middle houses gives the same total, so taking either middle house is correct.

## The two-part structure

cost[i][j] = the total distance for houses i..j served by one mailbox dp[i][g] = the best total for the first i houses using g mailboxes dp[i][g] = min over p of dp[p][g-1] + cost[p][i-1]

The interval table supplies the block costs and the partition table consumes them. Splitting the work that way keeps each half simple, and it is the same shape as problem 565.

## Boundaries

k equal to the number of houses answers 0: every house gets its own mailbox. 3 6 14 10 with k = 4 answers 0 and is the test.

k = 1 puts one mailbox at the median of everything. 7 4 6 1 with k = 1 answers 8, and it is deliberately unsorted so a solution that skips the sort gets a wrong median.

1 2 with k = 1 answers 1 and with k = 2 answers 0.

## Cost

Time O(n^2 k) for the partition plus O(n^2) to build the block costs if each is computed incrementally, or O(n^3) with the direct sum. Space O(n^2).

Constraints - `1 ≤ k ≤ n ≤ 100` - `1 ≤ position ≤ 10000` - the positions are distinct