给定两个数组 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)
最佳答案
这是 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))
。
关于algorithm - 给定 2 个非负数数组,找到乘积的最小和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33225258/