Post office problem – lintcode | Lxming's Weblog
This is a DP problem. We also need to pre-calculate the cost between any two points with a single post office. The DP formula is:
i: the number of post office
j: the jth house.
dp[i][j]: the minimal cost of having i post offices in houses [0]-[j]
cost[i][j]: the minimal cost of building a post office between i and j (inclusive).
dp[i][j] = Math.min(dp[i][j], dp[i – 1][l-1] + cost[l][j]);
Read full article from Post office problem – lintcode | Lxming's Weblog
No comments:
Post a Comment