给定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],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))。