Computing the minimal flexible distance of two vectors using dynamic programming 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 &lt; o and j &gt; u or i &gt; o and
j &lt; 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.
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)$?