mahmoud_arafa's blog

DP Problems(involving printing the optimal items)
By mahmoud_arafa, 10 years ago, In English

Hi.

I'm looking for DP problems that involve printing the items that give the optimal answer(involves reconstructing the optimal items), like printing the Knapsack items for example.

If you know any similar problems, please comment with them.

Thanks in advance.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem 1 Problem 2

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

1) Print longest common subsequence of two strings/arrays.

2) Print longest increasing subsequence of an array.(I can do it in O(N^2), can someone tell me how to do it in O(N*logN), please?)

3) http://acm.timus.ru/problem.aspx?space=1&num=1303

4) http://acm.timus.ru/problem.aspx?num=1112

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    • Compress the numbers so that they are all in the range 1..N.
    • Build a segment tree that stores the length of the LIS that ends with each number 1..N.
    • Then the pseudocode would be something like this...
    for(int i=1; i<=N; i++)
{
  int lis = query(1, A[i]-1) + 1;
  update(A[i], lis);
}

    If you want to print the actual sequence too, you can also store the node where you "come from" in each node in the tree. The optimum answer will be contained in some leaf of the tree.

    → Reply