LeetCode 题解工作台
最小移动总距离
X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [position j , limit j ] ，表示第 j 个工厂的位置在 position j ，且第 j 个工…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们先对机器人和工厂进行升序排列。然后定义函数 $dfs(i, j)$ 表示从第 个机器人开始，第 个工厂开始维修的最小总移动距离。 对于 $dfs(i, j)$，如果第 个工厂不维修机器人，那么 $dfs(i, j)=dfs(i, j+1)$。如果第 个工厂维修机器人，我们可以枚举第 个工厂维修的机器人的数量，找出最小的总移动距离。即 $dfs(i, j) = \min(dfs(i +…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。
每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。
所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。
任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。
请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。
注意：
- 所有机器人移动速度相同。
- 如果两个机器人移动方向相同，它们永远不会碰撞。
- 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
- 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
- 机器人从位置
x到位置y的移动距离为|y - x|。
示例 1：
输入：robot = [0,4,6], factory = [[2,2],[6,2]] 输出：4 解释：如上图所示： - 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。 - 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。 - 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。 第一个工厂的维修上限是 2 ，它维修了 2 个机器人。 第二个工厂的维修上限是 2 ，它维修了 1 个机器人。 总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。
示例 2：
输入：robot = [1,-1], factory = [[-2,1],[2,1]] 输出：2 解释：如上图所示： - 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。 - 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。 第一个工厂的维修上限是 1 ，它维修了 1 个机器人。 第二个工厂的维修上限是 1 ，它维修了 1 个机器人。 总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。
提示：
1 <= robot.length, factory.length <= 100factory[j].length == 2-109 <= robot[i], positionj <= 1090 <= limitj <= robot.length- 测试数据保证所有机器人都可以被维修。
解题思路
方法一：记忆化搜索
我们先对机器人和工厂进行升序排列。然后定义函数 表示从第 个机器人开始，第 个工厂开始维修的最小总移动距离。
对于 ，如果第 个工厂不维修机器人，那么 。如果第 个工厂维修机器人，我们可以枚举第 个工厂维修的机器人的数量，找出最小的总移动距离。即 。
时间复杂度 ，空间复杂度 。其中 和 分别为机器人数量和工厂数量。
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
@cache
def dfs(i, j):
if i == len(robot):
return 0
if j == len(factory):
return inf
ans = dfs(i, j + 1)
t = 0
for k in range(factory[j][1]):
if i + k == len(robot):
break
t += abs(robot[i + k] - factory[j][0])
ans = min(ans, t + dfs(i + k + 1, j + 1))
return ans
robot.sort()
factory.sort()
ans = dfs(0, 0)
dfs.cache_clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \cdot n^2) |
| 空间 | O(m + S) |
面试官常问的追问
外企场景- question_mark
Ensure the candidate understands state transition dynamic programming and how it applies to minimizing the total distance.
- question_mark
Look for clear reasoning behind sorting robots and factories before applying dynamic programming.
- question_mark
Assess the candidate's ability to handle limits in factory repair capacity effectively.
常见陷阱
外企场景- error
Not sorting the robots and factories before applying dynamic programming, which may result in suboptimal solutions.
- error
Overcomplicating the problem by not recognizing the greedy approach to allocate robots to factories based on proximity.
- error
Failing to handle edge cases where factories have a repair limit of 0 or where robots are initially at the factory positions.
进阶变体
外企场景- arrow_right_alt
Consider variations where each robot has its own repair time, introducing a more complex allocation strategy.
- arrow_right_alt
Change the problem to a multidimensional dynamic programming approach where there are multiple repair factories along a multi-dimensional axis.
- arrow_right_alt
Introduce constraints where robots must be repaired in a specific order, adding a dependency to the dynamic programming approach.