Skip to content

2463. Minimum Total Distance Traveled 👍

  • Time: $O(|\texttt{robot}|^2|\texttt{factory}|)$
  • Space: $O(|\texttt{robot}|^2|\texttt{factory}|)$
 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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  long long minimumTotalDistance(vector<int>& robot,
                                 vector<vector<int>>& factory) {
    sort(robot.begin(), robot.end());
    sort(factory.begin(), factory.end());

    // dp[i][j][k] := min distance to fix robot[i:] with factory[j:] where
    // factory[j] already fixed k robots
    dp.resize(robot.size(),
              vector<vector<long long>>(factory.size(),
                                        vector<long long>(robot.size())));
    return minimumTotalDistance(robot, factory, 0, 0, 0);
  }

 private:
  vector<vector<vector<long long>>> dp;

  long long minimumTotalDistance(const vector<int>& robot,
                                 const vector<vector<int>>& factory, int i,
                                 int j, int k) {
    if (i == robot.size())
      return 0;
    if (j == factory.size())
      return LLONG_MAX;
    if (dp[i][j][k] > 0)
      return dp[i][j][k];
    const long long skipFactory =
        minimumTotalDistance(robot, factory, i, j + 1, 0);
    const int position = factory[j][0];
    const int limit = factory[j][1];
    const long long useFactory =
        limit > k ? minimumTotalDistance(robot, factory, i + 1, j, k + 1) +
                        abs(robot[i] - position)
                  : LLONG_MAX / 2;
    return dp[i][j][k] = min(skipFactory, useFactory);
  }
};

 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
27
28
29
public class Solution {
  public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
    Collections.sort(robot);
    Arrays.sort(factory, (a, b) -> (a[0] - b[0]));

    // dp[i][j][k] := min distance to fix robot[i:] with factory[j:] where
    // factory[j] already fixed k robots
    dp = new long[robot.size()][factory.length][robot.size()];
    return minimumTotalDistance(robot, factory, 0, 0, 0);
  }

  private long[][][] dp;

  private long minimumTotalDistance(List<Integer> robot, int[][] factory, int i, int j, int k) {
    if (i == robot.size())
      return 0;
    if (j == factory.length)
      return Long.MAX_VALUE;
    if (dp[i][j][k] > 0)
      return dp[i][j][k];
    final long skipFactory = minimumTotalDistance(robot, factory, i, j + 1, 0);
    final int position = factory[j][0];
    final int limit = factory[j][1];
    final long useFactory = limit > k ? minimumTotalDistance(robot, factory, i + 1, j, k + 1) +
                                            Math.abs(robot.get(i) - position)
                                      : Long.MAX_VALUE / 2;
    return dp[i][j][k] = Math.min(skipFactory, useFactory);
  }
}

 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:
    robot.sort()
    factory.sort()

    # dp(i, j, k) := min distance to fix robot[i:] with factory[j:] where
    # factory[j] already fixed k robots
    @functools.lru_cache(None)
    def dp(i: int, j: int, k: int) -> int:
      if i == len(robot):
        return 0
      if j == len(factory):
        return math.inf
      skipFactory = dp(i, j + 1, 0)
      position, limit = factory[j]
      useFactory = dp(i + 1, j, k + 1) + abs(robot[i] - position) \
          if limit > k else math.inf
      return min(skipFactory, useFactory)

    return dp(0, 0, 0)