thảo luận Leetcode mỗi ngày

var minimumTotalDistance = function (robot, factory) {
  robot.sort((u, v) => u - v);
  factory = factory
    .sort((u, v) => u[0] - v[0])
    .flatMap(([x, c]) => Array(c).fill(x));
  const memo = [];
  const minCost = (u, v) => {
    memo[u] ??= [];
    return (memo[u][v] ??= (() => {
      if (u < v) {
        return +Infinity;
      }
      if (v === 0) {
        return 0;
      }
      return Math.min(
        minCost(u - 1, v - 1) + Math.abs(factory[u - 1] - robot[v - 1]),
        minCost(u - 1, v)
      );
    })());
  };
  return minCost(factory.length, robot.length);
};

class Solution {
    final long MAX_VALUE = (long) 1e12;
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        robot.sort(Comparator.comparingInt(a -> a));
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);
        List<Integer> factoryPositions = new ArrayList<>();
        for (int[] f : factory) {
            for (int i = 0; i < f[1]; i++) {
                factoryPositions.add(f[0]);
            }
        }
        int robotNum = robot.size();
        int factoryNum = factoryPositions.size();
        long[][] dp = new long[robotNum + 1][factoryNum + 1];
        for (int i = 1; i <= robotNum; i++) {
            dp[i][0] = MAX_VALUE;
        }
        for (int i = 1; i <= robotNum; i++) {
            for (int j = 1; j <= factoryNum; j++) {
                long distance = Math.abs(robot.get(i - 1) - factoryPositions.get(j - 1)) + dp[i - 1][j - 1];
                long skipFactory = dp[i][j - 1];
                dp[i][j] = Math.min(distance, skipFactory);
            }
        }
        return dp[robotNum][factoryNum];
    }
}

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot = sorted(robot)
        factory = sorted(factory)

        limits = []
        for p, l in factory:
            for i in range(l):
                limits.append(p)

        n = len(robot)
        m = len(limits)

        cache = [[-1 for _ in range(m)] for _ in range(n)]
        def dfs(i, j):
            if i == n:
                return 0
            if j == m or n - i > m - j:
                return inf

            if cache[i][j] != -1:
                return cache[i][j]
            
            take = abs(robot[i] - limits[j]) + dfs(i + 1, j + 1)
            skip = dfs(i, j + 1)

            cache[i][j] = min(take, skip)
            return cache[i][j]

        return dfs(0, 0)

const INF: i64 = i64::MAX;

impl Solution {
    pub fn minimum_total_distance(robot: Vec<i32>, factory: Vec<Vec<i32>>) -> i64 {
        fn top_down(
            robot_index: usize,
            factory_index: usize,
            factory_capacity: usize,
            robots: &[i32],
            factories: &[(i32, i32)],
            memo: &mut Vec<Vec<Vec<i64>>>
        ) -> i64 {
            if robot_index == robots.len() {
                return 0;
            }

            if factory_index == factories.len() {
                return INF;
            }

            if factory_capacity == 0 {
                return (
                    top_down(
                        robot_index,
                        factory_index + 1,
                        if factory_index + 1 == factories.len() { 0 } else { factories[factory_index + 1].1 as usize },
                        robots,
                        factories,
                        memo
                    )
                );
            }

            if memo[robot_index][factory_index][factory_capacity] != -1 {
                return memo[robot_index][factory_index][factory_capacity];
            }

            memo[robot_index][factory_index][factory_capacity] = INF;

            let mut repair_at_current_factory_result =
                top_down(
                    robot_index + 1,
                    factory_index,
                    factory_capacity - 1,
                    robots,
                    factories,
                    memo
                );

            if repair_at_current_factory_result < INF {
                repair_at_current_factory_result +=
                    (robots[robot_index] - factories[factory_index].0).abs() as i64;
            }

            let repair_at_next_factory_result =
                top_down(
                    robot_index,
                    factory_index + 1,
                    if factory_index + 1 == factories.len() { 0 } else { factories[factory_index + 1].1 as usize },
                    robots,
                    factories,
                    memo
                );

            let min_distance = INF.min(repair_at_current_factory_result).min(repair_at_next_factory_result);
            memo[robot_index][factory_index][factory_capacity] = min_distance;

            min_distance
        }

        let mut robots = robot;

        let mut factories: Vec<(i32, i32)> =
            factory.into_iter().map(|fact| (fact[0], fact[1])).collect();

        let mut memo = vec![vec![vec![-1; 101]; 101]; 101];

        robots.sort_unstable();
        factories.sort_unstable();

        top_down(0, 0, factories[0].1 as usize, &robots, &factories, &mut memo)
    }
}