Dynamic programming problem

[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) | xik - yk |,
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 :)