Trying to understand this Dynamic Programming solution

Question

The problem is as follows.

Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq m$.

So, we can use two list of indexes $\ I$, $J$, such that $I\subseteq [n]$, $J\subset [m]$, and $|I|=|J|=n$. The notation is $[m] = \{1,2,3,\cdots, m\}$.

Therefore, our goal reduces to:

$$ \min_{k=1,2,\cdots, n} \{|a_{i_k} - b_{j_k}|\ : i_k\in [n],\ j_k\in J\}.$$

I found the problem above in this question (in other words) and trying to understand how the answer provided there, it attempts to solve the problem with dynamic programming.

This is what I understand:

• I believe we are building two indexes and are pairing them.
• We first sort boys by height
• Somehow we then construct a match, but it's not greedy, is it? it utilizes calculating the sum of the absolute difference in height. How was the pairing constructed?

This paragraph is key and I would love to understand it but I don't get it:

you can use dynamic programming to find the optimal matching by building up 
optimal matchings that have the first j boys in sorted height order all 
paired up somehow among the first k girls in sorted height order (where 
j≤k), and using the optimal matchings for the values (j,k−1) and (j−1,k−1)to 
decide the optimal matching for the values (j,k), based on whether you pair 
up boy j with girl k or not. 

So, the question is how the dynamic programing method is working here based on the answer given and pseudo code of the solution it would be helpful.

Answer 1

We are going to build up the matching with a top-bottom approach. Before proceed your intuition is correct. We need two indexes for our solution, that it would be a recursive function $f$ based on a index $i\in [n]$ and index $j\in[m]$.

This is the definition for $f$. $$f(i,j):= \text{The optimal* matching between the elements from }\{a_1, a_2, \cdots, a_i \}\text{ with $i$ elements from } \{b_1, b_2, \cdots, b_j\}.$$

The first thing as with other recursive methods, is establish the well-defined bases cases of the recursion. These are the following. $$ \begin{align} f(i,1) &= |a_i - b_1|\ \ \ \forall i\in [n]\\ f(1,j) &= \min\ \{\ f(1, j-1),\ |a_1 - b_j|\ \} \ \ \ \forall j\in [m]\\ \end{align} $$ These are when we have just one element from $B$ and just one element from $A$, respectively.

Thinking like $f$ is working yet as we expected, we can define it as follows with $i\in [n]$ and $j\in [m]$.

$$ f(i,j) = \min \ \begin{cases} f(i-1, j-1) + |a_i - b_j| & \text{we match $a_i$ with $b_j$}\\ f(i, j-1)&\text{we won't pair $a_i$ with $b_j$} \end{cases}. $$

Be aware in the recursion for the corner cases, these are when $f$ is not defined. They are when $i$ or $j$, or even both are less than or equal to zero, for these cases, we are gonna say, $f(i,j) = \infty$.

So, what is the answer (?). Because, we are using top-bottom approach and based on the definition of $f$, after compute $f(n, m)$, it should give us the answer. Notice, that this way is one of many methods using dynamic programming, and sincerely, it is almost the same as the solution your provided in the link, but here it is just more explicit.

Maybe like a pseudocode, we can do this in Python with the following implementation.

@memo
def f(n, m):
    global a, b
    if m <= 0 or n <= 0:
        return float('inf')
    if n == 1:
        return min(f(1, m - 1), abs(a[0] - b[m - 1]))
    if m == 1:
        return abs(a[n-1] - b[0])
    x = f(n - 1, m - 1) + abs(a[n - 1] - b[m - 1])  # take b_m
    y = f(n, m - 1)  # dont take b_m
    return min(x, y)

print f(len(a), len(b))

My @memo decorator is the following, and is the key of a technique that involved dynamic programing, caching o memoization. from functools import wraps def memo(func): # memoization cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap