本文共 862 字，大约阅读时间需要 2 分钟。

一条直线上有N个居民点，需要建设K个邮局，邮局只能建在居民点上，则所有居民点到最近邮局到最短距离是？

动态规划，时间O(N*N)

核心思想：

外层循环，邮局数量K，直到包括最大邮局： 中层循环，区间[0,R]，直到包括整个区间： 内层循环，从[0,R]区间k个邮局，扩展到[0,R]区间k+1个邮局需要枚举R次。

总时间复杂度O(NNK)，后面进行细节和时间优化。

---

接下来分析具体过程：

dp表设置如下：dp[i][j]表示i个邮局在区间[0,j]上的最短距离。

则方法为，先左向右，再上至下填整个dp表。

从[0,R]区间k个邮局，扩展[0,R]区间k+1个邮局到方法：

依次 计算k个区间负责[0,L] 和 1个区间负责[L+1,R] 的总距离，取最小的一个， 即 dp[k+1][R] = min{ dp[k][L] + w[L+1][R] }

其中，w[i][j] 为辅助表，存储只建一个邮局在区间[i…j]上的总距离，方便计算。

---

预处理w表时间优化：

快速求解w[i][j]的办法，贪心思想直接找中点，这里找左中点，即L/2，稍加思考发现，左右中点的解是一样的。

但是，枚举所有区间[i…j]的中点，时间复杂度为O(N*N)，依然可以优化。

w[i][j] 和 w[i][j-1] 有如下关系：

w[i][j] = w[i][j-1] + Arr[j] - Arr[(i+j)/2]，无论区间[i…j]为奇偶长度，这个式子都成立，这里Arr[i]是居民点坐标。

求解w表，时间复杂度，降为O(N)

---

dp核心思想时间优化：至时间O(N*N)

最内层循环枚举过程可以降至O(1)，利用四边形不等式，大概思想如下：

若已知[0,L]由k个邮局负责，[L+1][R]由1个邮局负责，是dp[k+1][R]上最小距离。

那么， 当求解dp[k+2][R]时，最小值一定存在于[0,L+t]由k+1个邮局负责，[L+t+1][R]由1个邮局负责。 此时，需要一个额外数组L[k][R]，记录dp[k][R]最小值时，L的位置。

---

转载地址：http://wdwji.baihongyu.com/