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?