I'm having problem to solve this problem in DP:(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Dynamic programming problem

**Physics Forums | Science Articles, Homework Help, Discussion**