Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Dynamic programming problem

  1. Jan 22, 2012 #1
    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
  2. jcsd
  3. Jan 22, 2012 #2
    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
    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.
  4. Jan 22, 2012 #3
    That's great! Thanks :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook