題意
在 X 軸上有一些機器人和工廠。給定一個整數陣列 robot，其中 robot[i] 是第 i 個機器人的位置。再給定一個二維整數陣列 factory，其中 factory[j]=[positionj,limitj]，表示第 j 個工廠的位置是 positionj，且第 j 個工廠最多可以修理 limitj 個機器人。
每個機器人的位置是 唯一 的。每個工廠的位置也是 唯一 的。注意，機器人最初可以 與工廠在相同位置。
所有機器人最初都是損壞的；它們會朝一個方向持續移動。方向可以是 X 軸的負方向或正方向。當機器人到達一個未達到其限制的工廠時，工廠會修理該機器人，並且機器人停止移動。
在任何時刻，你可以為 某些 機器人設置初始移動方向。你的目標是最小化所有機器人移動的總距離。
返回 所有機器人移動的最小總距離。測試案例生成確保所有機器人都能得到修理。
注意：
- 所有機器人以相同速度移動。
- 如果兩個機器人朝相同方向移動，它們永遠不會相撞。
- 如果兩個機器人朝相反方向移動並在某處相遇，它們不會相撞。它們會交錯而過。
- 如果機器人經過一個達到其限制的工廠，它會如同該工廠不存在般穿過。
- 如果機器人從位置 x 移動到位置 y，則其移動的距離是 ∣y−x∣。
約束條件
- 1≤robot.length,factory.length≤100
- factory[j].length=2
- −109≤robot[i],positionj≤109
- 0≤limitj≤robot.length
- 測試數據保證所有機器人都能被修理。
思路
為使移動距離最小，每個 factory 應該修一段連續位置上的機器人，可以用反證法證明。假設在能構成最短的一段距離的狀況下，某個 factory 修了不相連的機器人，則可以把其中一個機器人換到其他 factory 修，其他機器人位置不變，這樣能使新的總距離小於等於原來的總距離，與假設矛盾。
因此，我們可以將機器人和工廠按照位置排序，然後考慮每個工廠負責修理其附近的一段連續機器人。這樣可以確保每個工廠修理的機器人彼此間距離最小化，從而總距離也達到最小。
方法一：記憶化搜尋(Memoization)
在得到上述結論後，我們可以寫出遞迴式，來計算每個工廠修理不同數量機器人所需的距離，並使用 記憶化搜尋(Memoization) 來避免計算重複的子問題。
定義 dfs(i,j) 為前 i+1 個工廠修理 j+1 個機器人所需的最小距離，則可以透過枚舉第 i 個工廠修理 k+1 個機器人，來遞迴地計算 dfs(i,j)。
dfs(i,j)=min{dfs(i−1,j)dfs(i−1,j−(k+1))+∑p=0k∣robot[j−p]−positioni∣工廠 i 修 0 個機器人工廠 i 修 k+1 個機器人
注意到在計算 ∑p=0k∣robot[j−p]−positioni∣ 的過程中，從 k 到 k′=k+1 時，只需加上 ∣robot[j−k′]−positioni∣ 即可，因此可以透過前綴和來優化。此外，第 i 個工廠最多可以修理 limiti 個機器人，因此 k 的範圍是 0≤k≤min(limiti−1,j)。
接著考慮邊界條件：
- 當 i<0 時，表示已經考慮完所有工廠，如果此時還有機器人未修理，代表不合法，返回 ∞；否則返回 0。
- 當 j<0 時，表示已經修理完所有機器人，可以提早剪枝，直接返回 0。
最後，直接返回 dfs(m−1,n−1) 即可。
複雜度分析
- 時間複雜度：O(m×n2)，其中 m 是工廠數量，n 是機器人數量。
- 總共有 m×n 個狀態，每個狀態需要枚舉修理的機器人數量 k 做轉移，而 k 的最大值為 n，因此在轉移時需要處理 O(n) 種可能。
- 空間複雜度：O(m×n)，用於儲存記憶化搜索的結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
n, m = len(robot), len(factory)
robot.sort()
factory.sort()
@cache
def dfs(i: int, j: int) -> int:
if i < 0:
return 0 if j < 0 else float('inf')
if j < 0:
return 0
res = dfs(i - 1, j)
dist = 0
pos, limit = factory[i]
for k in range(limit):
if j - k < 0:
break
dist += abs(robot[j - k] - pos)
res = min(res, dist + dfs(i - 1, j - (k + 1)))
return res
return dfs(m - 1, n - 1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n = robot.size(), m = factory.size();
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<vector<long long>> memo(m, vector<long long>(n, LLONG_MAX / 2));
auto dfs = [&](auto&& dfs, int i, int j) -> long long {
if (i < 0) return j < 0 ? 0 : LLONG_MAX / 2;
if (j < 0) return 0;
long long& res = memo[i][j];
if (res != LLONG_MAX / 2) return res;
res = dfs(dfs, i - 1, j);
long long dist = 0;
int pos = factory[i][0], limit = factory[i][1];
for (int k = 0; k < limit && k <= j; ++k) {
dist += abs(robot[j - k] - pos);
res = min(res, dist + dfs(dfs, i - 1, j - (k + 1)));
}
return res;
};
return dfs(dfs, m - 1, n - 1);
}
};
|
方法二：Bottom-Up DP
同樣地，我們可以透過將 Top-Down 的記憶化搜索改為 Bottom-Up 的動態規劃來解決這個問題。
但我們在遞迴時，是用 i<0 和 j<0 來作為邊界條件，因此我們需要將陣列的索引整體偏移 1，並且將 f[0][0] 初始化為 0。定義 f[i][j] 為前 i 個工廠修理 j 個機器人所需的最小距離，則可以透過枚舉第 i 個工廠修理 k 個機器人，來計算 f[i][j]。
f[i][j]=0≤k≤min(limiti,j)min{f[i−1][j−k]+p=1∑k∣robot[j−p]−positioni∣}
由於在 Top-Down 的記憶化搜索中，我們是從大到小計算，因此 Bottom-Up 的動態規劃中，我們需要從小到大計算。
最後，直接返回 f[m][n] 即可。
複雜度分析
- 時間複雜度：O(m×n2)，其中 m 是工廠數量，n 是機器人數量。
- 總共有 m×n 個狀態，每個狀態需要枚舉修理的機器人數量 k 做轉移，而 k 的最大值為 n，因此在轉移時需要處理 O(n) 種可能。
- 空間複雜度：O(m×n)，用於儲存動態規劃的結果。
雖然複雜度相同，但 Bottom-Up 的動態規劃不用使用額外的堆疊空間，此外，也能繼續優化空間複雜度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
n, m = len(robot), len(factory)
robot.sort()
factory.sort()
f = [[float('inf')] * (n + 1) for _ in range(m + 1)]
f[0][0] = 0
for i, (pos, limit) in enumerate(factory, 1):
for j in range(n + 1):
f[i][j] = f[i - 1][j]
dist = 0
for k in range(1, limit + 1):
if j - k < 0:
break
dist += abs(robot[j - k] - pos)
f[i][j] = min(f[i][j], dist + f[i - 1][j - k])
return f[m][n]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n = robot.size(), m = factory.size();
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<vector<long long>> f(m + 1, vector<long long>(n + 1, LLONG_MAX / 2));
f[0][0] = 0;
for (int i = 1; i <= m; ++i) {
int pos = factory[i - 1][0], limit = factory[i - 1][1];
for (int j = 0; j <= n; ++j) {
f[i][j] = f[i - 1][j];
long long dist = 0;
for (int k = 1; k <= limit && k <= j; ++k) {
dist += abs(robot[j - k] - pos);
f[i][j] = min(f[i][j], dist + f[i - 1][j - k]);
}
}
}
return f[m][n];
}
};
|
方法二空間優化一：滾動陣列(Rolling Array)
在方法二的 Bottom-Up 動態規劃中，我們需要一個二維陣列 f[i][j] 來存儲狀態。然而，我們可以觀察到，在計算 f[i][j] 時，只需要依賴於前一個工廠的狀態 f[i−1][j′]，也就是只會用到前一個橫列的結果，因此我們可以透過 滾動陣列(Rolling Array) 來優化空間複雜度，每次只保留前一個橫列的結果，並且在計算完後更新為當前橫列的結果。
我們保留大部分的程式碼，只將原本的 f 從二維陣列改為一維陣列，並且額外新增一個 fnew 來儲存當前橫列的結果，在計算完當前橫列後更新 f 為 fnew。
最後，返回 f[n] 即可。
複雜度分析
- 時間複雜度：O(m×n2)，與方法二相同。
- 空間複雜度：O(n)，只需要 兩個 一維陣列來存儲當前的最小距離結果。
這種優化將空間複雜度從原本的 O(m×n) 降低到了 O(n)。然而，由於我們只是改變了儲存方式，並沒有改變計算邏輯，所以時間複雜度保持不變。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
n, m = len(robot), len(factory)
robot.sort()
factory.sort()
f = [0] + [float('inf')] * n
for pos, limit in factory:
new_f = f.copy()
for j in range(n + 1):
new_f[j] = f[j]
dist = 0
for k in range(1, limit + 1):
if j - k < 0:
break
dist += abs(robot[j - k] - pos)
new_f[j] = min(new_f[j], dist + f[j - k])
f = new_f
return f[n]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n = robot.size(), m = factory.size();
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<long long> f(n + 1, LLONG_MAX / 2);
f[0] = 0;
for (int i = 0; i < m; ++i) {
int pos = factory[i][0], limit = factory[i][1];
vector<long long> new_f = f;
for (int j = 0; j <= n; ++j) {
new_f[j] = f[j];
long long dist = 0;
for (int k = 1; k <= limit && k <= j; ++k) {
dist += abs(robot[j - k] - pos);
new_f[j] = min(new_f[j], dist + f[j - k]);
}
}
f = new_f;
}
return f[n];
}
};
|
方法二空間優化二：反向遍歷
在方法二計算 f[i][j] 時，除了轉移來源只依賴於前一個工廠的狀態 f[i−1][j′] 外， 也必定滿足 j′≤j，且當 j′=j 時，f[i][j]=f[i−1][j]。因此，如果我們能控制 j′ 的遍歷順序，確保在轉移時不會使用到已經被更新的結果，那麼我們就能只用一個一維陣列來儲存 f[i][j] 的結果。
在上個方法中，我們是從小到大遍歷 j，因此我們可以改為從大到小遍歷 j，這樣一來，在計算 f[i][j] 時，就不會使用到已經被更新的結果，也就是只會用到 f[i−1][j′]，其中 j′≤j，因此在使用 f[i−1][j′] 時，j′ 必定還未被更新。
這與背包問題中類似，透過在適當的時候反向遍歷，從而確保在更新時不會使用到被「汙染」的結果。
複雜度分析
- 時間複雜度：O(m×n2)，與方法二相同。
- 空間複雜度：O(n)，只需要 一個 一維陣列來存儲當前的最小距離結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
n, m = len(robot), len(factory)
robot.sort()
factory.sort()
f = [0] + [float('inf')] * n
for pos, limit in factory:
for j in range(n, -1, -1):
dist = 0
for k in range(1, limit + 1):
if j - k < 0:
break
dist += abs(robot[j - k] - pos)
f[j] = min(f[j], dist + f[j - k])
return f[n]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
int n = robot.size(), m = factory.size();
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
vector<long long> f(n + 1, LLONG_MAX / 2);
f[0] = 0;
for (int i = 0; i < m; ++i) {
int pos = factory[i][0], limit = factory[i][1];
for (int j = n; j >= 0; --j) {
long long dist = 0;
for (int k = 1; k <= limit && k <= j; ++k) {
dist += abs(robot[j - k] - pos);
f[j] = min(f[j], dist + f[j - k]);
}
}
}
return f[n];
}
};
|
寫在最後
Cover photo is remixed from @hans, thanks for their work!
