Minimum Total Distance Traveled | Leetcode 2463 | DP | RECURSION | Hard | Java | Developer Coder

[@DeveloperCoder]

Recursion+Memo
class Solution {
public long minimumTotalDistance(List robot, int[][] factory) {
Collections.sort(robot);
Arrays.sort(factory, Comparator.comparingInt(a -> a[0]));
List factoryPositions = new ArrayList();
for(int[] f : factory ){
for(int i=0;i

[@DeveloperCoder]

DP:
class Solution {
public long minimumTotalDistance(List robot, int[][] factory) {
Collections.sort(robot);
Arrays.sort(factory, Comparator.comparingInt(a -> a[0]));
List factoryPositions = new ArrayList();
for (int[] f : factory) {
for (int i = 0; i < f[1]; i++) {
factoryPositions.add(f[0]);
}
}
int robotCount = robot.size();
int factoryCount = factoryPositions.size();
long[] next = new long[factoryCount+1];
long[] current = new long[factoryCount+1];
for( int i=robotCount -1;i>=0;i--){
//no factories left case
if(i!= robotCount -1 ) next[factoryCount] = (long) 1e12;
current[factoryCount] = (long) 1e12;
for(int j = factoryCount -1 ;j>=0;j--){
//assign current robot to current factory
long assign = Math.abs((long) robot.get(i) - factoryPositions.get(j)) + next[j+1];
//skip current factory for this robot
long skip = current[j+1];
//take the min option
current[j] = Math.min(assign,skip);
}
System.arraycopy(current,0,next,0,factoryCount+1);
}
return current[0];
}
}

[@arihantsinghrana2173]

can you provide the code
for both approaches

[@DeveloperCoder]

Sure, I have added the code in comments.😊

[@arihantsinghrana2173]

@@DeveloperCoder Thank brother