- #1
ydan87
- 25
- 0
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
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