Post office problem – lintcode | Lxming's Weblog

Post office problem – lintcode | Lxming's Weblog

Post office problem – lintcode

http://www.lintcode.com/en/problem/post-office-problem/#

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