# Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements

So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if the list A is [a,b,c] and the list B is [d,f,g], a valid merge between the two may be [d,a,f,b,g,c], or even just the concatenation of both: [a,b,c,d,f,g], but not [b,c,f,d,c,g,a]. I know I have in total $$\binom{|A| + |B|}{|A|}$$ ways of merging these lists and maintaining this property, however I have to select one based on the following constraint:

Every pair of exercises $$(e_1,e_2)$$ has a burnout function $$\delta : (e_i,e_j) \mapsto \mathbb{Z}$$ associated to them, and I want to obtain a merged list resulting from the lists $$r_1 = [e_{11},e_{12},\ldots,e_{1n}]$$ and $$r_2 = [e_{21},e_{22},\ldots,e_{2n}]$$ such that the total sum resulting of adding every pair of elements applied to the function $$\delta$$ in $$r_3$$ is minimum, that is to say, that the following sum applied to $$r_3$$ is the minimum possible.

$$\sum_{i=0,j=i+1}^{n-1} \delta(r_3[i],r_3[j])$$

I was able to solve this using a brute force approach, so basically calculating the $$\binom{|A| + |B|}{|A|}$$ lists that maintain relative order, and then just calculating the total sum in everyone of them and keeping the one with minimum total sum.

An example would be:

$$r_1 = [\text{scissor kicks}, \text{scissor kicks}]$$

$$r_2 = [\text{mountain climbers},\text{mountain climbers}]$$

$$\delta(\text{scissor kicks}, \text{mountain climbers}) = 4$$

$$\delta(\text{mountain climbers}, \text{scissor kicks}) = 3$$

$$\delta(\text{mountain climbers}, \text{mountain climbers}) = 10$$

$$\delta(\text{scissor kicks}, \text{scissor kicks}) = 10$$

In this case, merging these two lists maintaining relative order while at the same time minimizing the total sum would result in $$r_3 = [\text{mountain climbers},\text{scissor kicks},\text{mountain climbers},\text{scissor kicks}]$$, which has a total sum of 10.

I know this problem can be solved using a dynamic programming approach in polynomial time however I've not been able to think of a solution yet.

• I suggest you follow the advice in cs.stackexchange.com/tags/dynamic-programming/info for how to systematically approach dynamic programming problems and tell us how far you got. Have you found a recursive algorithm (even one that takes exponential time)? – D.W. Apr 21 at 5:57
• @D.W. I’d say my main problem so far is not having been able to think of a recursive solution. – Jere Apr 21 at 13:07
• If you read through the resources there, they give you a systematic way to try to come up with a recursive solution, by suggesting different subproblems you can try to use. Why don't you show your attempts to construct a recursive algorithm for each of the plausible subproblem definitions suggested by the methods there? – D.W. Apr 21 at 16:15