@SomeBottle 在 Leetcode每日一题 —— 2463. 最小移动总距离 中发帖
机器人怎么又回来了 (ᵕ—ᴗ—)
这题想起来还挺有难度,每个机器人的选择会影响到其他机器人的选择,大概能猜到是动态规划。看了提示和标签才知道怎么定义递推数组。
思路
代价和工厂、机器人的位置有关,首先为了方便递推,先对两个输入序列按位置进行排序。
递推数组 dp[i][j] 定义为前 i 个工厂修理前 j 个机器人所要的最小总移动距离。注意这里的“前”,为了方便处理边界,这里 i 和 j 从 1 开始。
初始化
对于 dp[i][0],前 i 个工厂处理前 0 个机器人,一个都不处理当然就是 dp[i][0]=0 了。
对于 dp[0][j], j=1...nRobot,前 0 个工厂处理前 j 个机器人,没有处理机器人的能力,因此设为一个很大的值 dp[0][j]=1e12。
递推
按照先 i=1...nFactory 后 j=1...nRobot 的顺序推就行。
递推...