一、贪心性质
看上去，一个工厂修理一段连续的机器人是最优的。为什么？
先排序，设工厂的位置为 $f_1 < f_2 < \cdots < f_n$，机器人的位置为 $r_1 < r_2 < \cdots < r_m$。
注：题目保证工厂的位置互不相同，机器人的位置互不相同。
对于序列中的两个工厂 $f_a$ 和 $f_b$（$a<b$），两个机器人 $r_i$ 和 $r_j$（$i<j$），对比如下两个方案：
- $r_i$ 去 $f_a$，$r_j$ 去 $f_b$，移动距离之和为 $|r_i - f_a| + |r_j - f_b|$。
- $r_i$ 去 $f_b$，$r_j$ 去 $f_a$，移动距离之和为 $|r_i - f_b| + |r_j - f_a|$。
下图是其中一种情况。
{:width=600px}
用分类讨论可以证明，$|r_i - f_a| + |r_j - f_b|\le |r_i - f_b| + |r_j - f_a|$。
换句话说，存在这样的最优解，对于任意一对机器人 $i$ 和 $j$（$i<j$），机器人 $i$ 去的工厂编号 $\le $ 机器人 $j$ 去的工厂编号。同一个工厂修理的机器人，在排序后的机器人序列里是连续的一段。
二、寻找子问题
在示例 1 中，我们要解决的问题（原问题）是：
- 工厂下标区间 $[0,1]$ 修理机器人下标区间 $[0,2]$，机器人移动的最小总距离。
从右往左思考，枚举最后一个工厂修多少个机器人：
- 修 $0$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,2]$，机器人移动的最小总距离。
- 修 $1$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,1]$，机器人移动的最小总距离。
- 修 $2$ 个机器人，问题变成：工厂 $[0,0]$ 修理机器人 $[0,0]$，机器人移动的最小总距离。
- 至多修 $2$ 个，因为 $\textit{limit}_1 = 2$。
这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。
注：从右往左思考，主要是方便把递归翻译成递推。从左往右思考也是可以的。
三、状态定义与状态转移方程
根据上面的讨论，定义 $\textit{dfs}(i,j)$ 表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j]$，机器人移动的最小总距离。
枚举工厂 $i$ 修 $k=0,1,2\ldots,\min(j+1,\textit{limit}_i)$ 个机器人，问题变成工厂下标区间 $[0,i-1]$ 修理机器人下标区间 $[0,j-k]$，机器人移动的最小总距离，即 $\textit{dfs}(i-1, j-k)$，再加上机器人 $[j-k+1, j]$ 到工厂 $i$ 的距离。
对所有 $k$ 取最小值，就得到了 $\textit{dfs}(i,j)$，即
$$
\textit{dfs}(i,j) = \min_{k=0}^{\min(j+1,\textit{limit}i)} \left{ \textit{dfs}(i-1, j-k) + \sum{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]| \right}
$$
由于 $k$ 每增加 $1$，距离和 $\displaystyle\sum_{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]|$ 就会新增一项 $|\textit{robot}[j-k+1]-\textit{position}[i]|$，所以可以用一个变量 $\textit{disSum}$ 维护距离和，而不是对每个 $k$ 都跑一个循环算距离和。
递归边界：
- $\textit{dfs}(i,-1)=0$。没有机器人了，总移动距离为 $0$。
- $\textit{dfs}(-1,j)=\infty\ (j\ge 0)$。没有工厂，但还有剩下的机器人，不合法。返回 $\infty$，这样上面公式中的 $\min$ 不会取到不合法的情况。
递归入口：$\textit{dfs}(n-1,m-1)$，这是原问题，也是答案。
注：题目保证所有机器人都可以被维修。
四、递归搜索 + 保存递归返回值 = 记忆化搜索
考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：
- 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\textit{memo}$ 数组中。
- 如果一个状态不是第一次遇到（$\textit{memo}$ 中保存的结果不等于 $\textit{memo}$ 的初始值），那么可以直接返回 $\textit{memo}$ 中保存的结果。
⚠注意：$\textit{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\textit{dfs}(i,j)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。
Python 用户可以无视上面这段，直接用 @cache 装饰器。
关于记忆化搜索的原理，请看视频讲解 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】，其中包含把记忆化搜索 1:1 翻译成递推的技巧。
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
factory.sort(key=lambda f: f[0])
robot.sort()
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, j: int) -> int:
if j < 0: # 所有机器人都修完了
return 0
if i < 0: # 还有机器人没修，但没有工厂了
return inf
# 工厂 i 不修机器人
res = dfs(i - 1, j)
position, limit = factory[i]
dis_sum = 0
# 枚举修 k 个机器人
for k in range(1, min(j + 1, limit) + 1):
dis_sum += abs(robot[j - k + 1] - position)
res = min(res, dfs(i - 1, j - k) + dis_sum)
return res
return dfs(len(factory) - 1, len(robot) - 1)
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int n = factory.length;
int m = robot.length;
long[][] memo = new long[n][m];
for (long[] row : memo) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
return dfs(n - 1, m - 1, robot, factory, memo);
}
private long dfs(int i, int j, int[] robot, int[][] factory, long[][] memo) {
if (j < 0) { // 所有机器人都修完了
return 0;
}
if (i < 0) { // 还有机器人没修，但没有工厂了
return Long.MAX_VALUE / 2; // 避免加法溢出
}
if (memo[i][j] != -1) { // 之前计算过
return memo[i][j];
}
// 工厂 i 不修机器人
long res = dfs(i - 1, j, robot, factory, memo);
int position = factory[i][0];
int limit = factory[i][1];
long disSum = 0;
// 枚举修 k 个机器人
for (int k = 1; k <= Math.min(j + 1, limit); k++) {
disSum += Math.abs(robot[j - k + 1] - position);
res = Math.min(res, dfs(i - 1, j - k, robot, factory, memo) + disSum);
}
memo[i][j] = res; // 记忆化
return res;
}
}
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
ranges::sort(factory, {}, [](auto& f) { return f[0]; });
ranges::sort(robot);
int n = factory.size(), m = robot.size();
vector memo(n, vector<long long>(m, -1)); // -1 表示没有计算过
auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
if (j < 0) { // 所有机器人都修完了
return 0;
}
if (i < 0) { // 还有机器人没修，但没有工厂了
return LLONG_MAX / 2; // 避免加法溢出
}
long long& res = memo[i][j]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
// 工厂 i 不修机器人
res = dfs(i - 1, j);
int position = factory[i][0], limit = factory[i][1];
long long dis_sum = 0;
// 枚举修 k 个机器人
for (int k = 1; k <= min(j + 1, limit); k++) {
dis_sum += abs(robot[j - k + 1] - position);
res = min(res, dfs(i - 1, j - k) + dis_sum);
}
return res;
};
return dfs(n - 1, m - 1);
}
};
func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)
n, m := len(factory), len(robot)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, m)
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var dfs func(int, int) int
dfs = func(i, j int) (res int) {
if j < 0 { // 所有机器人都修完了
return 0
}
if i < 0 { // 还有机器人没修，但没有工厂了
return math.MaxInt / 2 // 避免加法溢出
}
p := &memo[i][j]
if *p != -1 { // 之前计算过
return *p
}
defer func() { *p = res }() // 记忆化
// 工厂 i 不修机器人
res = dfs(i-1, j)
position, limit := factory[i][0], factory[i][1]
disSum := 0
// 枚举修 k 个机器人
for k := 1; k <= min(j+1, limit); k++ {
disSum += abs(robot[j-k+1] - position)
res = min(res, dfs(i-1, j-k)+disSum)
}
return
}
return int64(dfs(n-1, m-1))
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm^2 + n\log n)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(nm)$，单个状态的计算时间为 $\mathcal{O}(m)$，所以记忆化搜索的时间复杂度为 $\mathcal{O}(nm^2)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度，由于 $\mathcal{O}(m\log m)$ 比 $\mathcal{O}(nm^2)$ 小，可以省略。
- 空间复杂度：$\mathcal{O}(nm)$。保存多少状态，就需要多少空间。
五、1:1 翻译成递推
我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。
具体来说，$f[i+1][j+1]$ 的定义和 $\textit{dfs}(i,j)$ 的定义是一样的，都表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j]$，机器人移动的最小总距离。这里 $+1$ 是为了把 $\textit{dfs}(i,-1)$ 和 $\textit{dfs}(-1,j)$ 也翻译过来，这样我们可以把 $f[i][0]$ 和 $f[0][j]$ 作为初始值。
相应的递推式（状态转移方程）也和 $\textit{dfs}$ 一样：
$$
f[i+1][j+1] = \min_{k=0}^{\min(\textit{limit}i, j+1)} \left{ f[i][j-k+1] + \sum{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]| \right}
$$
初始值 $f[i][0] = 0$ 以及 $f[0][j] = \infty\ (j\ge 1)$，翻译自递归边界。
答案为 $f[n][m]$，翻译自递归入口。
写法一
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
factory.sort(key=lambda f: f[0])
robot.sort()
n, m = len(factory), len(robot)
f = [[0] * (m + 1) for _ in range(n + 1)]
f[0][1:] = [inf] * m
for i, (position, limit) in enumerate(factory):
for j in range(m):
# 工厂 i 不修机器人
res = f[i][j + 1]
# 枚举修 k 个机器人
dis_sum = 0
for k in range(1, min(j + 1, limit) + 1):
dis_sum += abs(robot[j - k + 1] - position)
res = min(res, f[i][j - k + 1] + dis_sum)
f[i + 1][j + 1] = res
return f[n][m]
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int n = factory.length;
int m = robot.length;
long[][] f = new long[n + 1][m + 1];
Arrays.fill(f[0], Long.MAX_VALUE / 2);
f[0][0] = 0;
for (int i = 0; i < n; i++) {
int position = factory[i][0];
int limit = factory[i][1];
for (int j = 0; j < m; j++) {
// 工厂 i 不修机器人
long res = f[i][j + 1];
// 枚举修 k 个机器人
long disSum = 0;
for (int k = 1; k <= Math.min(j + 1, limit); k++) {
disSum += Math.abs(robot[j - k + 1] - position);
res = Math.min(res, f[i][j - k + 1] + disSum);
}
f[i + 1][j + 1] = res;
}
}
return f[n][m];
}
}
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
ranges::sort(factory, {}, [](auto& f) { return f[0]; });
ranges::sort(robot);
int n = factory.size(), m = robot.size();
vector f(n + 1, vector<long long>(m + 1));
fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);
for (int i = 0; i < n; i++) {
int position = factory[i][0], limit = factory[i][1];
for (int j = 0; j < m; j++) {
// 工厂 i 不修机器人
long long res = f[i][j + 1];
// 枚举修 k 个机器人
long long dis_sum = 0;
for (int k = 1; k <= min(j + 1, limit); k++) {
dis_sum += abs(robot[j - k + 1] - position);
res = min(res, f[i][j - k + 1] + dis_sum);
}
f[i + 1][j + 1] = res;
}
}
return f[n][m];
}
};
func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)
n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}
for i, fac := range factory {
position, limit := fac[0], fac[1]
for j := range m {
// 工厂 i 不修机器人
res := f[i][j+1]
// 枚举修 k 个机器人
disSum := 0
for k := 1; k <= min(j+1, limit); k++ {
disSum += abs(robot[j-k+1] - position)
res = min(res, f[i][j-k+1]+disSum)
}
f[i+1][j+1] = res
}
}
return int64(f[n][m])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
写法二
为了方便大家阅读下一章（单调队列优化），先微调一下状态定义和状态转移方程。
把 $j+1$ 替换成 $j$，定义 $f[i+1][j]$ 表示工厂下标区间 $[0,i]$ 修理机器人下标区间 $[0,j-1]$，机器人移动的最小总距离。
状态转移方程为：
$$
f[i+1][j] = \min_{k=0}^{\min(\textit{limit}i, j)} \left{ f[i][j-k] + \sum{p=j-k}^{j-1} |\textit{robot}[p]-\textit{position}[i]| \right}
$$
这样可以少写很多 $+1$。
在 $k$ 从 $0$ 增大到 $\min(\textit{limit}_i, j)$ 的过程中，$j-k$ 从 $j$ 减小到 $\max(j-\textit{limit}_i, 0)$。
把 $j-k$ 替换成 $k$，状态转移方程为：
$$
f[i+1][j] = \min_{k=\max(j-\textit{limit}i, 0)}^{j} \left{ f[i][k] + \sum{p=k}^{j-1} |\textit{robot}[p]-\textit{position}[i]| \right}
$$
这样转移方程就更干净了，从而方便我们进一步优化。
注：这相当于在枚举工厂 $i$ 修理的最左边的机器人的编号 $k$。
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
factory.sort(key=lambda f: f[0])
robot.sort()
n, m = len(factory), len(robot)
f = [[0] * (m + 1) for _ in range(n + 1)]
f[0][1:] = [inf] * m
for i, (position, limit) in enumerate(factory):
for j in range(1, m + 1):
# 工厂 i 不修机器人
res = f[i][j]
# 修理下标在 [k, j-1] 中的机器人
dis_sum = 0
for k in range(j - 1, max(j - limit, 0) - 1, -1):
dis_sum += abs(robot[k] - position)
res = min(res, f[i][k] + dis_sum)
f[i + 1][j] = res
return f[n][m]
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int n = factory.length;
int m = robot.length;
long[][] f = new long[n + 1][m + 1];
Arrays.fill(f[0], Long.MAX_VALUE / 2);
f[0][0] = 0;
for (int i = 0; i < n; i++) {
int position = factory[i][0];
int limit = factory[i][1];
for (int j = 1; j <= m; j++) {
// 工厂 i 不修机器人
long res = f[i][j];
// 修理下标在 [k, j-1] 中的机器人
long disSum = 0;
for (int k = j - 1; k >= Math.max(j - limit, 0); k--) {
disSum += Math.abs(robot[k] - position);
res = Math.min(res, f[i][k] + disSum);
}
f[i + 1][j] = res;
}
}
return f[n][m];
}
}
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
ranges::sort(factory, {}, [](auto& f) { return f[0]; });
ranges::sort(robot);
int n = factory.size(), m = robot.size();
vector f(n + 1, vector<long long>(m + 1));
fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);
for (int i = 0; i < n; i++) {
int position = factory[i][0], limit = factory[i][1];
for (int j = 1; j <= m; j++) {
// 工厂 i 不修机器人
long long res = f[i][j];
// 修理下标在 [k, j-1] 中的机器人
long long dis_sum = 0;
for (int k = j - 1; k >= max(j - limit, 0); k--) {
dis_sum += abs(robot[k] - position);
res = min(res, f[i][k] + dis_sum);
}
f[i + 1][j] = res;
}
}
return f[n][m];
}
};
func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)
n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}
for i, fac := range factory {
position, limit := fac[0], fac[1]
for j := 1; j <= m; j++ {
// 工厂 i 不修机器人
res := f[i][j]
// 修理下标在 [k, j-1] 中的机器人
disSum := 0
for k := j - 1; k >= max(j-limit, 0); k-- {
disSum += abs(robot[k] - position)
res = min(res, f[i][k]+disSum)
}
f[i+1][j] = res
}
}
return int64(f[n][m])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm^2 + n\log n)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。DP 的时间复杂度为 $\mathcal{O}(nm^2)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度，由于 $\mathcal{O}(m\log m)$ 比 $\mathcal{O}(nm^2)$ 小，可以省略。
- 空间复杂度：$\mathcal{O}(nm)$。
六、单调队列优化
前置题目：239. 滑动窗口最大值，视频讲解 单调队列【基础算法精讲 27】。
定义 $d_i[p] = |\textit{robot}[p]-\textit{position}[i]|$。
设 $d_i$ 数组的前缀和数组为 $s_i$。关于 $s_i$ 的定义，请看 前缀和。
状态转移方程为：
$$
\begin{aligned}
f[i+1][j] &= \min_{k=\max(j-\textit{limit}i, 0)}^{j} \left{ f[i][k] + s_i[j] - s_i[k]\right} \
&= s_i[j] + \min{k=\max(j-\textit{limit}_i, 0)}^{j} \left{ f[i][k] - s_i[k]\right} \
\end{aligned}
$$
当 $j$ 增大时，$k$ 的范围是一个向右移动的滑动窗口，我们计算的是 $f[i][k] - s_i[k]$ 的滑动窗口最小值。上式的 $\min$ 可以用单调队列优化至均摊 $\mathcal{O}(1)$ 时间复杂度。
答疑
问：对于单调队列优化 DP，什么时候先把元素入队再计算 DP，什么时候先计算 DP 再把元素入队？
答：这取决于计算的 DP 是否包含要入队的元素。如果包含，那就先入队再计算 DP；如果不包含，那就先计算 DP 再入队。本题是前者。
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
factory.sort(key=lambda f: f[0])
robot.sort()
n, m = len(factory), len(robot)
f = [[0] * (m + 1) for _ in range(n + 1)]
f[0][1:] = [inf] * m
for i, (position, limit) in enumerate(factory):
dis_sum = list(accumulate((abs(r - position) for r in robot), initial=0)) # 前缀和
q = deque([(0, 0)])
for j in range(1, m + 1):
# 1. 入
v = f[i][j] - dis_sum[j]
while q and q[-1][1] >= v:
q.pop()
q.append((j, v))
# 2. 出
while q[0][0] < j - limit:
q.popleft()
# 3. 队首为滑动窗口最小值
f[i + 1][j] = dis_sum[j] + q[0][1]
return f[n][m]
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int n = factory.length;
int m = robot.length;
long[][] f = new long[n + 1][m + 1];
Arrays.fill(f[0], Long.MAX_VALUE / 2);
f[0][0] = 0;
for (int i = 0; i < n; i++) {
int position = factory[i][0];
int limit = factory[i][1];
long[] disSum = new long[m + 1]; // 前缀和
for (int j = 0; j < m; j++) {
disSum[j + 1] = disSum[j] + Math.abs(robot[j] - position);
}
Deque<long[]> q = new ArrayDeque<>();
q.offerLast(new long[]{0, 0});
for (int j = 1; j <= m; j++) {
// 1. 入
long v = f[i][j] - disSum[j];
while (!q.isEmpty() && q.peekLast()[1] >= v) {
q.pollLast();
}
q.offerLast(new long[]{j, v});
// 2. 出
while (q.peekFirst()[0] < j - limit) {
q.pollFirst();
}
// 3. 队首为滑动窗口最小值
f[i + 1][j] = disSum[j] + q.peekFirst()[1];
}
}
return f[n][m];
}
}
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
ranges::sort(factory, {}, [](auto& f) { return f[0]; });
ranges::sort(robot);
int n = factory.size(), m = robot.size();
vector f(n + 1, vector<long long>(m + 1));
fill(f[0].begin() + 1, f[0].end(), LLONG_MAX / 2);
for (int i = 0; i < n; i++) {
int position = factory[i][0], limit = factory[i][1];
vector<long long> dis_sum(m + 1); // 前缀和
for (int j = 0; j < m; j++) {
dis_sum[j + 1] = dis_sum[j] + abs(robot[j] - position);
}
deque<pair<int, long long>> q;
q.emplace_back(0, 0);
for (int j = 1; j <= m; j++) {
// 1. 入
long long v = f[i][j] - dis_sum[j];
while (!q.empty() && q.back().second >= v) {
q.pop_back();
}
q.emplace_back(j, v);
// 2. 出
while (q.front().first < j - limit) {
q.pop_front();
}
// 3. 队首为滑动窗口最小值
f[i + 1][j] = dis_sum[j] + q.front().second;
}
}
return f[n][m];
}
};
func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)
n, m := len(factory), len(robot)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, m+1)
}
for j := 1; j <= m; j++ {
f[0][j] = math.MaxInt / 2
}
for i, fac := range factory {
position, limit := fac[0], fac[1]
disSum := make([]int, m+1) // 前缀和
for j, r := range robot {
disSum[j+1] = disSum[j] + abs(r-position)
}
type pair struct{ i, v int }
q := []pair{{0, 0}}
for j := 1; j <= m; j++ {
// 1. 入
v := f[i][j] - disSum[j]
for len(q) > 0 && q[len(q)-1].v >= v {
q = q[:len(q)-1]
}
q = append(q, pair{j, v})
// 2. 出
for q[0].i < j-limit {
q = q[1:]
}
// 3. 队首为滑动窗口最小值
f[i+1][j] = disSum[j] + q[0].v
}
}
return int64(f[n][m])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm + n\log n + m\log m)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。对于三重循环里面的二重循环，站在每个元素的视角看，这个元素在二重循环中最多入队出队各一次，因此二重循环的循环次数之和是 $\mathcal{O}(m)$，所以三重循环的时间复杂度是 $\mathcal{O}(nm)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度。
- 空间复杂度：$\mathcal{O}(nm)$。
七、空间优化
观察上面的代码，计算 $f[i+1][j]$ 只会用到 $f[i][j]$。
所以只需要一个长为 $m+1$ 的一维数组 $f$，我们直接把计算结果覆盖到 $f[j]$ 中。
此外，前缀和可以一边枚举 $j$ 一边计算，从而优化成一个变量。
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
factory.sort(key=lambda f: f[0])
robot.sort()
m = len(robot)
f = [0] + [inf] * m
for position, limit in factory:
dis_sum = 0
q = deque([(0, 0)])
for j, r in enumerate(robot, 1): # r = robot[j - 1]
dis_sum += abs(r - position)
# 1. 入
v = f[j] - dis_sum
while q and q[-1][1] >= v:
q.pop()
q.append((j, v))
# 2. 出
while q[0][0] < j - limit:
q.popleft()
# 3. 队首为滑动窗口最小值
f[j] = dis_sum + q[0][1]
return f[m]
// 更快的写法见【Java 写法二】
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int m = robot.length;
long[] f = new long[m + 1];
Arrays.fill(f, Long.MAX_VALUE / 2);
f[0] = 0;
for (int[] fac : factory) {
int position = fac[0];
int limit = fac[1];
long disSum = 0;
Deque<long[]> q = new ArrayDeque<>(); // ArrayDeque 慢，更快的写法见【Java 写法二】
q.offerLast(new long[]{0, 0});
for (int j = 1; j <= m; j++) {
disSum += Math.abs(robot[j - 1] - position);
// 1. 入
long v = f[j] - disSum;
while (!q.isEmpty() && q.peekLast()[1] >= v) {
q.pollLast();
}
q.offerLast(new long[]{j, v});
// 2. 出
while (q.peekFirst()[0] < j - limit) {
q.pollFirst();
}
// 3. 队首为滑动窗口最小值
f[j] = disSum + q.peekFirst()[1];
}
}
return f[m];
}
}
class Solution {
public long minimumTotalDistance(List<Integer> robotList, int[][] factory) {
int[] robot = robotList.stream().mapToInt(i -> i).toArray();
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int m = robot.length;
long[] f = new long[m + 1];
Arrays.fill(f, Long.MAX_VALUE / 2);
f[0] = 0;
int[] idxQ = new int[m + 1]; // 用两个数组模拟 ArrayDeque
long[] valQ = new long[m + 1];
for (int[] fac : factory) {
int position = fac[0];
int limit = fac[1];
long disSum = 0;
int head = 0;
int tail = 0;
idxQ[tail] = 0;
valQ[tail] = 0;
for (int j = 1; j <= m; j++) {
disSum += Math.abs(robot[j - 1] - position);
// 1. 入
long v = f[j] - disSum;
while (head <= tail && valQ[tail] >= v) {
tail--;
}
tail++;
idxQ[tail] = j;
valQ[tail] = v;
// 2. 出
while (idxQ[head] < j - limit) {
head++;
}
// 3. 队首为滑动窗口最小值
f[j] = disSum + valQ[head];
}
}
return f[m];
}
}
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
ranges::sort(factory, {}, [](auto& f) { return f[0]; });
ranges::sort(robot);
int m = robot.size();
vector<long long> f(m + 1, LLONG_MAX / 2);
f[0] = 0;
for (auto& fac : factory) {
int position = fac[0], limit = fac[1];
long long dis_sum = 0;
deque<pair<int, long long>> q;
q.emplace_back(0, 0);
for (int j = 1; j <= m; j++) {
int r = robot[j - 1];
dis_sum += abs(r - position);
// 1. 入
long long v = f[j] - dis_sum;
while (!q.empty() && q.back().second >= v) {
q.pop_back();
}
q.emplace_back(j, v);
// 2. 出
while (q.front().first < j - limit) {
q.pop_front();
}
// 3. 队首为滑动窗口最小值
f[j] = dis_sum + q.front().second;
}
}
return f[m];
}
};
func minimumTotalDistance(robot []int, factory [][]int) int64 {
slices.SortFunc(factory, func(a, b []int) int { return a[0] - b[0] })
slices.Sort(robot)
m := len(robot)
f := make([]int, m+1)
for j := 1; j <= m; j++ {
f[j] = math.MaxInt / 2
}
for _, fac := range factory {
position, limit := fac[0], fac[1]
disSum := 0
type pair struct{ i, v int }
q := []pair{{0, 0}}
for j, r := range robot {
j++
disSum += abs(r - position)
// 1. 入
v := f[j] - disSum
for len(q) > 0 && q[len(q)-1].v >= v {
q = q[:len(q)-1]
}
q = append(q, pair{j, v})
// 2. 出
for q[0].i < j-limit {
q = q[1:]
}
// 3. 队首为滑动窗口最小值
f[j] = disSum + q[0].v
}
}
return int64(f[m])
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
复杂度分析
- 时间复杂度：$\mathcal{O}(nm + n\log n + m\log m)$，其中 $n$ 是 $\textit{factory}$ 的长度，$m$ 是 $\textit{robot}$ 的长度。对于三重循环里面的二重循环，站在每个元素的视角看，这个元素在二重循环中最多入队出队各一次，因此二重循环的循环次数之和是 $\mathcal{O}(m)$，所以三重循环的时间复杂度是 $\mathcal{O}(nm)$。剩下的 $\mathcal{O}(n\log n + m\log m)$ 是排序的时间复杂度。
- 空间复杂度：$\mathcal{O}(m)$。忽略排序的栈开销。
专题训练
见下面动态规划题单的「五、划分型 DP」和「§11.3 单调队列优化 DP」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
欢迎关注 B站@灵茶山艾府
登录
