CODEWITHSUNDEEP
pythonalgorithmrecursiondynamic-programming
GKroch
GKroch

Reputation: 83

Maximal sum of products of two lists

I need to write an algorithm based on dynamic programming approach and to be honest I got completely stuck.

Ok, so the problem is like that. I have two lists with the same (even) length. For example let's say that:

a = [43, 10, 40, 12]
b = [63, 73, 5,  13]

I need to use the dynamic programming approach to find maximal sum of products of paired numbers from those lists. The numbers can be only paired in such a way that:

(a[n] * a[n+1]) V (b[n] * b[n+1]) V (a[n] * b[n])

And obviously if you chose one of those combinations you can't use those numbers anymore.

What I actually need help with is finding the recursive function for that. And I really can't find it. Would be really grateful if someone could give me a hand with that.

Best regards

Upvotes: 0

Views: 167

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32627

The key insight here is that the matchings are coupled. If you match a[i] to a[i+1], you also have to match b[i] to b[i+1]. Otherwise, there would be at least one unmatched entry. Therefore, as you walk through the list from left to right, you only have to decide whether to match vertically or horizontally.

To formulate this as a dynamic program, we propagate the function S(i) that records the maximum score that can be achieved using elements 0 .. i. The recursive relation is then:

S(i) = max(
            S(i - 1) + a[i] * b[i],                        #vertical match
            S(i - 2) + a[i - 1] * a[i] + b[i - 1] * b[i])  #horizontal match

Of course, with appropriate boundary handling.

Upvotes: 1

Related Questions