Given two arrays A
and B
, each containing n
non-negative numbers, remove a>0
elements from the end of A and b>0
elements from the end of B. Evaluate the cost of such an operation as X*Y
where X
is the sum of the a
elements removed from A
and Y
the sum of the b
elements removed from B
. Keep doing this until both arrays are empty. The goal is to minimize the total cost.
Using dynamic programming and the fact that an optimal strategy will always take exactly one element from either A
or B
I can find an O(n^3) solution. Now I'm curious to know if there is an even faster solution to this problem?
EDIT: Stealing an example from @recursive in the comments:
A = [1,9,1] and B = [1, 9, 1]. Possible to do with a cost of 20. (1) * (1 + 9) + (9 + 1) * (1)
Here's O(n^2)
. Let CostA(i, j)
be the min cost of eliminating A[1..i], B[1..j]
in such a way that the first removal takes only one element from B
. Let CostB(i, j)
be the min cost of eliminating A[1..i], B[1..j]
in such a way that the first removal takes only one element from A
. We have mutually recursive recurrences
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))
with base cases
CostA(0, 0) = 0
CostA(>0, 0) = infinity
CostA(0, >0) = infinity
CostB(0, 0) = 0
CostB(>0, 0) = infinity
CostB(0, >0) = infinity.
The answer is min(CostA(n, n), CostB(n, n))
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With