algorithm - 给定 2 个非负数数组，找到乘积的最小和

Question

给定两个数组 A和 B , 每个包含 n非负数，删除 a>0 A 和 b>0 末尾的元素B 末尾的元素。评估此类操作的成本 X*Y其中 X是 a 的总和从 A 中删除的元素和 Y b 的总和从 B 中删除的元素.继续这样做，直到两个数组都为空。目标是最小化总成本。

使用动态规划和最佳策略总是从 A 中恰好取一个元素这一事实或 B我可以找到一个 O(n^3) 解决方案。现在我很想知道这个问题是否有更快的解决方案？

编辑:从评论中的@recursive 窃取一个例子:

A = [1,9,1] and B = [1, 9, 1]. Possible to do with a cost of 20. (1) * (1 + 9) + (9 + 1) * (1)

Answer 1

这是 O(n^2)。设 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))。