World's most popular travel blog for travel bloggers.

# [Solved]: Using dynamic programming to find the number ofl increasing subsequences

, ,
Problem Detail:

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing sub-sequences for every index j, that end with Xj.

My solution should include a recurrence formula that solves this problem in O(n^2) and a correctness proof, I was only able to solve it using a nested for loop and I'm not sure if there's an O(n^2) recursion solution.

``List a[1…n] <- [1…1]  For j= 1 to n     For i= 1 to j-1        If xi<xj then           a[i]= a[j]+a[i];  ``

#### Answered By : babou

The recursive equivalent of what you wrote is:

``function S(j) is   r <- 1   For i <- 1 to j-1     if xi<xj then       r <- r+S(i)   return r ``

It is very similar to what you wrote, except that `a[1]` is replaced by `S(i`), i.e., a recursive call to the function, since it is the function that is supposed to compute the number of sequences that you store in `a[i]`. The array `a` is used to remember previous results, and the new result you are computing is obtained using the previous results.

This array is no longer needed, as it is replaced by the memoization of the dynamic programming interpretation of the recursive function. If I understood correctly what you are asking.

Now, to do the proof, you should explain why computing in this way is correct.

This works with the same costs as your algorithm, provided the recursion is interpreted with dynamic programming memomization, and you should be able to prove it easily.

Of course standard recursive execution of the function, without memoization of results, is a lot more costly.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44126

3.2K people like this

#### Post a Comment

Let us know your responses and feedback