这道题目需要我们在一个已经放置了若干物品的置物架上,找到放置新物品的最小移动成本。核心思路是检查所有可能的空隙和通过移动物品能创造的空隙,找到满足条件的最小移动次数。
具体步骤如下:
有一个长度为 N 的置物架,上面一级放置着 M 个物品,每个物品大小不同,占用了置物架不同大小的长度空间,且物品之间不一定连续放置,可能存在空隙。现在你想放置你自己的物品,且希望在保持物品原有顺序的情况下,尽可能不去移动置物架上已存在的物品,即你的策略是:
1.如果存在足够的长度空间能放置你的物品,则直接放置你的物品,此时移动的物品数量为 0 ;
2.或者,你可以选择从 i 号物品开始的连续 K 个物品,将它们紧密排列,以获得空间,此时移动物品的数量为 K ,同时你将获得 K 个物品中间的空隙,i 号物品向前的空隙,以及 i+k 号物品向后的空隙,这三个空隙1的总和空间。
给你指定的长度、物品的排列,和你需要放置的物品大小,计算移动的物品数量的最小值。