Classical DP:

- f[house_i][k]: least cost if we set the k-
^{th}mailbox at house_i- f[house_i][k] = min(f[last_house_j][k-1] + cost=sum(min(dist(house_mid, house_i), dist(house_mid, house_j)) for i < mid < j)
- with pre-calculated cost, T(N) = O(NK * N).

- f[house_i][k]: least cost if we use k mailbox in range(i, n)
- f[house_i][k] = f[house_j][k-1] + cost in range(i, j)
- with pre-calculated cost, T(N) = O(N*N*K)