# Dynamic programming problem

1. Jan 22, 2012

### 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?

2. Jan 22, 2012

### 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:
Code (Text):

| 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.

3. Jan 22, 2012

### ydan87

That's great! Thanks :)