CODEWITHSUNDEEP
algorithmdynamic-programming
user1337
user1337

Reputation: 504

Given 2 arrays of non-negative numbers, find the minimum sum of products

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)

Upvotes: 6

Views: 1550

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

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)).

Upvotes: 4

Related Questions