您有一组n个对象,其中给出了整数位置.一组对象是同一位置的一组对象(不一定是该位置的所有对象:单个位置可能有多个组).对象可以向左或向右移动,目标是移动这些对象以形成k组,并在移动的最小距离的情况下移动.
例如:
我一直在尝试使用贪婪的方法(通过计算哪个移动最短),但这不起作用,因为每次移动都涉及两个可以移动的元素.我还没有能够制定动态编程方法,但我正在研究它.
据我了解，问题是：
我们在一条线上有 n 个点。我们想在线上放置 k 位置。我称它们为目的地。将 n 个点中的每一个移动到 k 个目的地之一，使距离之和最小。我把这个总和称为总成本。目的地可以重叠。
一个明显的事实是，对于每个点，我们应该寻找左侧最近的目的地和右侧最近的目的地，并选择最近的目的地。
另一个重要的事实是所有目的地都应该在要点上。因为我们可以将它们在线上向右或向左移动以到达某个点，而不会增加总距离。
根据这些事实考虑以下 DP 解决方案：
DP[i][j] 表示当我们只能使用 j 个目的地并且必须将目的地放在第 i 个点时，第 i 个点所需的最小总成本。
计算 DP[i][j] 确定第 i 个点之前的目的地（我们有 i 个选择），并且对于每个选择（例如第 k 个点）计算第 i 个点和添加的新点（第 k 个点）。将其与 DP[k][j - 1] 相加并找到所有 k 的最小值。
初始状态（例如 j = 1）和最终答案的计算留作练习！