Leetcode for Fun

Starts from July 02, 2020

Introduction:

Some logs to document the Leetcode questions (after found a job)


 
 
 
 
 
07/02/2020 15:55

1478. Allocate Mailboxes

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)