How to Solve This Dynamic Programming Problem with Two Subsequences?

[ydan87]

I'm having problem to solve this problem in DP:
Given 2 subsequences:

X = {x1, x2,..., xm} and Y = {y1, y2, ... , yn}

so `n <= m` and also `y1 <= y2 <= ... <= yn`.

The goal is to find a sub-sequence of `X` (xi1, xi2, ... , xin) such that:

sum(k is 1 to n) | xik - yk | is minimal

The DP algorithm should be `o(mn)`.

I though about that: define `B(i,j)` as the minimun sum so |Y| is j and |X| is I, but it seems I get stuck here.

Any help?
Thanks in advance

 

[Edgardo]

I think you are on the right track. Define B(i,j) as follows:

B(i,j): minimum of sum(k from 1 to j) | x_ik - y_k |,
where the first i elements of x and the first j elements of y are available.

---

So, basically you are searching for a "subset" of x. I recommend working on a related problem:
Consider the sequence A = [7, 2, 1, 3, 10]. Find a subset with 3 elements such that the sum of these elements is minimized. Let's call this the minimal subset of size 3.

Define B(i,j) as follows:
B(i,j): minimal subset of size j if the first i elements of A are available.

You would then write down a table:

    | j:    1    2    3
------------------------
i:
1   |      7         
2   |      2          
3   |      1
4   |      1
5   |      1

The first column is easy to fill out. Can you fill the rest?

I'm sure that if you can solve this problem you can also find a solution to your problem.

 

[ydan87]

That's great! Thanks :)