# Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised

Let's say we have two arrays m and n containing the characters from the set a, b, c , d, e. Assume each character in the set has a cost associated with it, consider the costs to be a=1, b=3, c=4, d=5, e=7.

for example

m = ['a', 'b', 'c', 'd', 'd', 'e', 'a']
n = ['b', 'b', 'b', 'a', 'c', 'e', 'd']


Suppose we would like to merge m and n to form a larger array s.

An example of s array could be

s = ['a', 'b', 'c', 'd', 'd', 'e', 'a', 'b', 'b', 'b', 'a', 'c', 'e', 'd']


or

s = ['b', 'a', 'd', 'd', 'd', 'b', 'e', 'c', 'b', 'a', 'b', 'a', 'c', 'e']


If there are two or more identical characters adjacent to eachother a penalty is applied which is equal to: number of adjacent characters of the same type * the cost for that character. Consider the second example for s above which contains a sub-array ['d', 'd', 'd']. In this case a penalty of 3*5 will be applied because the cost associated with d is 5 and the number of repetitions of d is 3.

I need to design a dynamic programming algorithm which minimises the cost associated with s.

Does anyone have any resources, papers, or algorithms they could share to help point me in the right direction?

• Please edit the question to show an merged array that minimises the cost associated. This is a general rule: always include an example that shows the expected correct answer. – Apass.Jack Apr 15 at 14:32
• Does s = ['b', 'a', 'd', 'b', 'd', 'e', 'd', 'c', 'b', 'a', 'b', 'a', 'c', 'e'] minimises the cost? – Apass.Jack Apr 15 at 15:48
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Apr 15 at 18:05
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – D.W. Apr 19 at 20:07

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible.

1. Count the total number of each character in $$m$$ and $$n$$. Let them be $$c(a), c(b), \cdots$$ respectively. Let $$x$$ be one of $$a,b,\cdots$$ such that $$c(x)$$ is the maximum.
2. Let $$\sigma$$ be the sum of all $$c(i)$$ where $$i$$ goes through $$a, b, \cdots$$ except $$x$$.
1. If $$c(x)\le 1 + \sigma$$, return 0.
2. Else return $$p(x)(c(x) -\sigma))$$, where $$p(x)$$ is the penalty associated with $$x$$.

The time-complexity of the algorithm is $$O(\ell)$$, where $$\ell$$ is the sum of the length of $$m$$ and the length of $$n$$.

Since the algorithm above is simple and clear, there is no need to apply the heavy machinery of dynamic programming.

### Exercises

Here are two exercises that prove the correctness of the algorithm above.

Exercise 1. If $$s(x)\le 1 + \sigma$$, design a procedure to produce a merged array that does not have adjacent pairs of the same letter.

Exercise 2. If $$s(x)\gt 1 + \sigma$$, then any merged array must have at least $$s(x) -\sigma$$ $$x$$s each of which is adjacent to another $$x$$. Design a procedure to produce a merged array that has no other penalties except for $$s(x) -\sigma$$ $$x$$s.

• it also needs to produce s – user102961 Apr 15 at 16:42
• @DanielPahor The statements in two exercises are hints for how to produce a merge array with the minimum penalty. Here is a further hint for exercise 2. Treat all characters other than $x$ as the same letter, say, $z$. – Apass.Jack Apr 15 at 18:30
• In fact I was thinking items coming from both lists have to respect initial order. It would have made DP relevant. But your answer is consistant with the question 2nd example... Now I just don't understand the need to have 2 lists. – Vince Apr 15 at 21:26
• @Vince I had thought the same as you before I posted my answer, as indicated by my comments to the question. DanielPahor, in case you had extra restrictions such as merging should be stable, i.e., the original array must be a subsequence of the merged array, please raise a new question. It would be great if you can add a reference to the problem or your motivation, bioinformatics. – Apass.Jack Apr 15 at 22:12