AlgorithmDP

LeetCode 2463 Minimum Total Distance Traveled

2026-04-15

題目

X 軸上有 $n$ 個 robot 跟 $m$ 個 factory，每個 factory 有位置跟維修上限。把每個 robot 分配到某個 factory 維修，最小化所有 robot 移動距離的總和。

$n, m \le 100$ ， $\sum \text{limit}_j \ge n$ ，座標與 limit 值域 $\le 10^9$ 。

做法

排序後做二維 DP，dp[i][j] = 前 $i$ 個 robot 用前 $j$ 個 factory 的最小距離。轉移枚舉第 $j$ 個 factory 修幾個 robot（0 到 limit[j]），每多修一個就加上對應的距離。

其實是直觀的二維匹配 DP，不過轉移的實作蠻不直觀的，是每日一題的實作練習好題。

Code

cpp

class Solution {
public:
    long long minimumTotalDistance(vector<int>& rb, vector<vector<int>>& fac) {
        sort(rb.begin(), rb.end());
        sort(fac.begin(), fac.end());
        int n = rb.size();
        int m = fac.size();
        long long dp[n+5][m+5];
        memset(dp, 0x3f, sizeof(dp));
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1 ; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int sum = 0;
                long long cost = 0;
                for (int k = 0; ;k++) {
                    if (i < k) break;
                    if (fac[j-1][1] < k) break;
                    if (k) {
                        cost += abs(rb[i-k] - fac[j-1][0]);
                    }
                    dp[i][j] = min(dp[i][j], dp[i-k][j-1] + cost);
                }
            }
        }
        return dp[n][m];
    }
};

複雜度

時間 $O(n \cdot m \cdot \text{max\_limit})$ ，空間 $O(n \cdot m)$ 。

Follow-up：DP 空間壓縮

轉移只依賴上一層 $j-1$ 的值，而且讀的是更小的 index dp[i-k][j-1]。跟 0-1 背包壓維的道理一樣，外層迴圈枚舉 factory，內層 $i$ 從 $n$ 往下掃，就能保證讀到的 dp[i-k] 還是上一輪的舊值。

空間從 $O(n \cdot m)$ 壓到 $O(n)$ ，時間不變。

cpp

class Solution {
public:
    long long minimumTotalDistance(vector<int>& rb, vector<vector<int>>& fac) {
        sort(rb.begin(), rb.end());
        sort(fac.begin(), fac.end());
        int n = rb.size();
        int m = fac.size();
        long long dp[n+5];
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for (int j = 0; j < m; j++) {
            for (int i = n; i >= 1; i--) {
                long long cost = 0;
                for (int k = 1; k <= min(i, fac[j][1]); k++) {
                    cost += abs(rb[i-k] - fac[j][0]);
                    dp[i] = min(dp[i], dp[i-k] + cost);
                }
            }
        }
        return dp[n];
    }
};

AlgorithmDPGreedyLeetCode Daily