给定两个非负数数组，求出乘积的最小和。

Question

给定两个数组A和B，每个数组都包含n非负数，从B结束时从A和b>0元素的末尾移除a>0元素。评估这样一个操作的成本，例如X是从A中删除的a元素和Y从B中删除的元素之和。继续这样做，直到两个数组都为空。目标是将总成本降到最低。

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

编辑:从注释中的@递归中窃取一个示例：

A= 1, 9，1和B= 1，9，1.费用为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))。