I have been trying to solve this problem my professor has given me but couldn't make a proper solution. The following is the problem
Problem: A rectangular circuit board has two parallel sides with width W between them. There are m terminals on the upper side of the board and n terminals (n < m) on the lower side. Let U1 < U[2] < … < U[m] be the distances from the left end of the board to the m terminals on the upper side, respectively. Let L1 < L[2] < … < L[n] be the distances from the left end of the board to the n terminals on the lower side, respectively. Now, we need to select n terminals from the m terminals on the upper side to be connected to the n terminals on the lower side by n straight line segments, respectively, such that the total length of the n line segments is minimized. The following figure illustrates the problem for m = 8 and n = 4.
(a) Prove that, in an optimal solution, any two line segments will not intersect.
(b) Design an O(mn) dynamic programming algorithm to solve this minimization problem. You need to define sub-problems, show the inductive formula, initial conditions, and a pseudocode. You can use d(i, j) to denote the distance between U[i] and L[j], 1 ≤ i ≤ m, 1 ≤ j ≤ n. (The calculation of d(i, j) = ) can be omitted.
My Approach:
For the above problem, my approach was first to make a matrix d(i,j) where i are the terminals on the bottom and j are the terminals on the top. d(i,j) has all the distances from any two circuits.Then iterating through each row I will find the smallest distance and mark the respective terminal. But I am not sure this would work if the top circuits are all to the extreme right of the side. So can anyone provide me with a better approach.