# ##### OPTIMIZED SOLUTION class Solution: def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int: rob_len=len(robot) robot.sort() factory.sort(key= lambda x: x[0]) all_factory=[] for i in factory: for j in range(i[1]): all_factory.append(i[0]) fac_len=len(all_factory) #print(all_factory) dp=[ [-1 for _ in range(fac_len)] for __ in range(rob_len)]
def func(rob_ind,fac_ind,r,f,distTravelled=0): nonlocal rob_len,fac_len if(rob_ind>=rob_len): return 0 if(fac_ind>=fac_len): return float('inf') #return result from cache, if it exists if(dp[rob_ind][fac_ind]!=-1): return dp[rob_ind][fac_ind] #assign distCovered=abs(r[rob_ind]-f[fac_ind]) k1=func(rob_ind+1,fac_ind+1,r,f,distTravelled+distCovered) #skip k2=func(rob_ind,fac_ind+1,r,f,distTravelled) ####cache the result dp[rob_ind][fac_ind]= min(k1+distCovered,k2) return dp[rob_ind][fac_ind]
ans=func(0,0,robot,all_factory,0) #print(dp) return ans
# ##### OPTIMIZED SOLUTION
class Solution:
def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
rob_len=len(robot)
robot.sort()
factory.sort(key= lambda x: x[0])
all_factory=[]
for i in factory:
for j in range(i[1]):
all_factory.append(i[0])
fac_len=len(all_factory)
#print(all_factory)
dp=[ [-1 for _ in range(fac_len)] for __ in range(rob_len)]
def func(rob_ind,fac_ind,r,f,distTravelled=0):
nonlocal rob_len,fac_len
if(rob_ind>=rob_len):
return 0
if(fac_ind>=fac_len):
return float('inf')
#return result from cache, if it exists
if(dp[rob_ind][fac_ind]!=-1):
return dp[rob_ind][fac_ind]
#assign
distCovered=abs(r[rob_ind]-f[fac_ind])
k1=func(rob_ind+1,fac_ind+1,r,f,distTravelled+distCovered)
#skip
k2=func(rob_ind,fac_ind+1,r,f,distTravelled)
####cache the result
dp[rob_ind][fac_ind]= min(k1+distCovered,k2)
return dp[rob_ind][fac_ind]
ans=func(0,0,robot,all_factory,0)
#print(dp)
return ans
Made This Video, on diwali day, I am sure, you would guessed that, hearing the sound, from the background.🤣
Happy Diwali !! 😄