hardDynamic Programming 2DPure DSA~50 min
Place K Mailboxes to Minimize Total Walk
Houses sit along a straight road at given positions. You install exactly k mailboxes anywhere on the road; each house walks to its nearest mailbox. Minimize the summed walking distance.
Problem
Given an array houses of distinct integer positions and an integer k, place k mailboxes (at any integer position) to minimize the total distance from each house to its nearest mailbox. Return that minimum total distance.
Input
An integer array houses and an integer k (1 <= k <= houses.length).
Output
An integer: the minimum total walking distance.
Constraints
- 1 <= houses.length <= 100
- 1 <= houses[i] <= 10^4
- 1 <= k <= houses.length
Examples
Example 1
Input
houses = [1,4,8,10,20], k = 3
Output
5
Mailboxes at 4, 9, 20: distances 3 + 0 + 1 + 1 + 0 = 5.
Example 2
Input
houses = [2,3,5,12,18], k = 2
Output
9
Best split groups {2,3,5} and {12,18} with medians, total 9.