Untitled

#include <vector>
#include <algorithm>
#include <climits>

int getMinTotalDistance(vector<int> dist_centers) {
    int n = dist_centers.size();
    
    // Sort the distribution centers
    sort(dist_centers.begin(), dist_centers.end());
    
    // Create a 2D DP table
    vector<vector<int>> dp(n, vector<int>(3, INT_MAX));
    
    // Base case: one warehouse serving all centers
    for (int i = 0; i < n; i++) {
        dp[i][0] = (i > 0 ? dp[i-1][0] : 0) + dist_centers[i] - dist_centers[0];
    }
    
    // Fill the DP table
    for (int k = 1; k < 3; k++) {
        for (int i = 0; i < n; i++) {
            int cost = 0;
            for (int j = i; j >= 0; j--) {
                cost += dist_centers[i] - dist_centers[j];
                if (j > 0) {
                    dp[i][k] = min(dp[i][k], dp[j-1][k-1] + cost);
                } else {
                    dp[i][k] = min(dp[i][k], cost);
                }
            }
        }
    }
    
    // Return the minimum total distance
    return dp[n-1][2];
}