给定两个非负数数组，找出它们的最小乘积之和。

Question

给定两个非负数数组，找出它们的最小乘积之和。

6

给定两个数组A和B，每个数组都包含n个非负整数，从A的末尾删除a个元素和从B的末尾删除b个元素。将这样的操作的成本评估为X*Y，其中X是从A中删除的a个元素的和，Y是从B中删除的b个元素的和。一直重复这样的操作，直到两个数组都为空。目标是最小化总成本。

使用动态规划，并且一个最优策略总是只从A或B中取一个元素，可以找到O(n^3)的解决方案。现在我想知道是否有更快的解决方案？

编辑：从评论@recursive中窃取一个示例：

A = [1,9,1]，B = [1, 9, 1]。可能以成本20进行操作。(1) * (1 + 9) + (9 + 1) * (1)

- user1337

根据您的陈述，我们需要从A的末尾和B的末尾进行删除。 - Laschet Jain

你的问题还是不太清晰。只需要从两个数组中依次弹出数字，将它们相乘并加到总和中即可。因为 (a1+a2)(b1+b2) >= a1b1 + a2 *b2。希望你明白我的意思。 - Laschet Jain

5

那并不总是产生最优的删除顺序: 例如, 当 A = [1,9,1] 和 B = [1, 9, 1] 时。你的方法得到了一个成本为83，但是有可能用20的成本完成。(1) * (1 + 9) + (9 + 1) * (1) - recursive

1

是的，有一个二次时间复杂度的解决方案。 - David Eisenstat

不过这是一份关于动态规划的本科练习，所以我没有去寻找一个。 - David Eisenstat

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

这里是一个时间复杂度为O(n²)的示例。令CostA(i,j)表示按照以下方式消除A[1..i]和B[1..j]所需的最小成本：第一次移除的元素只从B中选取。同样，令CostB(i,j)表示按照以下方式消除A[1..i]和B[1..j]所需的最小成本：第一次移除的元素只从A中选取。我们有相互递归的公式。

CostA(i, j) = A[i] * B[j] + min(CostA(i - 1, j),
                                CostA(i - 1, j - 1),
                                CostB(i - 1, j - 1))
CostB(i, j) = A[i] * B[j] + min(CostB(i, j - 1),
                                CostA(i - 1, j - 1),
                                CostB(i - 1, j - 1))

使用基本情况

CostA(0, 0) = 0
CostA(>0, 0) = infinity
CostA(0, >0) = infinity
CostB(0, 0) = 0
CostB(>0, 0) = infinity
CostB(0, >0) = infinity.

答案是min(CostA(n, n), CostB(n, n))。