Computing the minimal flexible distance of two vectors using dynamic programming

Question

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 i can only be matched with a point j if no point o is matched with a point u such that i < o and j > u or i > o and 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

Should output:

1.8 

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.

Answer 1

Since this is a programming assignment, I only show some hints.

Consider two vectors $\vec{a} = a_1 \cdots a_i \cdots a_m$ and $\vec{b} = b_1 \cdots b_j \cdots b_n$.

First, please prove the following

Observation: $a_m$ must be matched with $b_n$.

Second, consider the following subproblems,

$$D(i,j) \triangleq \text{the optimal (matching) distance between } a_1 \cdots a_i \text{ and } b_1 \cdots b_j.$$

and answer the following question

Given the observation above, what is the relationship between $D_{i,j}$ and $D(i-1, j)$, $D(i, j-1)$, or maybe $D(i-1, j-1)$?