I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim to minimize the total sum of distances between matched points with the following constraints:
- Every point from both vectors has to be matched at least once, but can be matched multiple times.
- A point
ican only be matched with a point
jif no point
ois matched with a point
i < oand
j > uor
i > oand
j < u, i.e., the ‘lines’ of the matches are not allowed to cross.
In order to compute the distance between two matched points, we use the absolute difference.
(Easy) Example input:
1.0 2.0 2.4 3.5 2.0 2.1 2.0 3.2
Because in this example
|1.0 - 2.0| + |2.0 - 2.1| + |2.4 - 2.0| + |3.5 - 3.2| is optimal
The assignment hints to sequence alignment which I thoroughly studied and came across the Needleman-Wunsch algorithm. However, I can't figure out how to adapt it to this problem.