algorithm - 对 DP 表中的一行进行排序以提取解决方案是否常见？

Question

我有两个长度相同的输入数组n包含正整数。n始终是偶数。使用此输入，我必须构建一个长度为n的新数组，其中包含每个输入数组的n/2 个元素，并且在新数组的每个索引处，必须有一个元素位于两个输入数组之一的相同索引处。新数组中所有条目的总和必须尽可能低。换句话说，我必须比较每个索引处的两个输入数组，并以使用每个数组的n/2个条目的方式选择它们以使总和尽可能低。

我的方法是创建一个 3 行的 DP 表。第 1 行是输入数组1 ，第 2行是输入数组2 ，第 3 行是差值（数组 1 - 数组 2）。为了提取解决方案，我将按照第 3 行的升序对表格进行排序。

我的问题是这是否是（常见的）做法或/以及是否有更好的解决方案。

排序前的DP表

排序后的DP表

标签： algorithmsortingrecursiondynamic

Answer 1

解决您的问题的可能方法是将 DP 状态定义为：-

Number of Elements that can be selected from Array1 :- n1

Number of Elements that can be selected from Array2 :- n2

Index of element in new array :- i

我们知道n1+ n2= n= 数组的长度。

和

n1= n2=n/2

所以在某种程度上，我们可以说n1和n2是相关的，因此只存储其中一个就足以定义一个 DP 状态。

DP状态：-(index, number of elements that can be selected from Array1)

初始状态：-(0,n/2)

过渡：- 在每个索引处，我们可以从 Array1 或 Array2 中选择元素，并且我们希望最小化成本。

f(i,x) = min(Array1[i]+f(i-1,x-1) , Array2[i]+f(i-1,x))

这个递归会给你答案。

构建一个 DP 表将在 O(n^2) 内解决这个问题。