Minimum Total Distance Traveled

Leetcode Problem:

• Minimum Total Distance Traveled

Summary

• Minimum Total Distance for Robots to Reach Factories

Approach

• Dynamic Programming with Memoization

Complexity

• O(n*m*log(n)+m*log(m))

Explanation

• This solution sorts the robots and factories by position, then uses dynamic programming with memoization to calculate the minimum total distance
• The `calculateMinDistance` function recursively tries two options: assigning the current robot to the current factory and skipping the current factory for the current robot
• The minimum of these two options is stored in the memo table to avoid repeated calculations.

Solution Code:

class Solution {
public:
    long long minimumTotalDistance(vector& robot,
                                   vector>& factory) {
        // Sort robots and factories by position
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());

        // Flatten factory positions according to their capacities
        vector factoryPositions;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) factoryPositions.push_back(f[0]);

        int robotCount = robot.size(), factoryCount = factoryPositions.size();
        vector> memo(robotCount,
                                       vector(factoryCount, -1));

        // Recursively calculate minimum total distance with memoization
        return calculateMinDistance(0, 0, robot, factoryPositions, memo);
    }

    long long calculateMinDistance(int robotIdx, int factoryIdx,
                                   vector& robot,
                                   vector& factoryPositions,
                                   vector>& memo) {
        // All robots assigned
        if (robotIdx == robot.size()) return 0;
        // No factories left to assign
        if (factoryIdx == factoryPositions.size()) return 1e12;
        // Check memo
        if (memo[robotIdx][factoryIdx] != -1) return memo[robotIdx][factoryIdx];

        // Option 1: Assign current robot to current factory
        long long assign = abs(robot[robotIdx] - factoryPositions[factoryIdx]) +
                           calculateMinDistance(robotIdx + 1, factoryIdx + 1,
                                                robot, factoryPositions, memo);

        // Option 2: Skip current factory for the current robot
        long long skip = calculateMinDistance(robotIdx, factoryIdx + 1, robot,
                                              factoryPositions, memo);

        return memo[robotIdx][factoryIdx] =
                   min(assign, skip);  // Take the minimum and store in memo
    }
};