In today's post, we briefly look at the longest common subsequence problem:
A longest common subsequence (LCS) is defined as a problem where two sequences are given X = (x1, x2, ... xm) and Y = (y1, y2, ... yn) and we wish to find a maximum length common subsequence of X and Y. A common subsequence is one that is a subsequence of both X and Y.
This is a standard textbook problem for dynamic programming. We solve this with the optimal substructure of an LCS and recursion.
We define the optimal substructure this way:
1. if xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1
2. if xm != yn, then zk != xm implies that Z is an LCS of Xm-1 and Y
3. if xm != yn, then zk != yn implies that Z is an LCS of X and Yn-1
In other words, we are defining the solution in terms of the subproblems.
This yields a recursive solution in terms of the length of the longest common subsequence c[i,j] as :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj
Condition number 2 limits which sub problems we should consider.
Also, there are overlapping sub-problems encountered something for which we could use bottom-up solving or memorization.
LCS-LENGTH(X, Y)
m = X.length
n = Y.length
initialize b[m,n] and c[m,n] as new tables
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b

and we print the LCS as
PRINT-LCS(b, X, i, j)
      if i == 0 or j == 0
        return
      if b[i,j] == up-left
         PRINT-LCS(b, X, i-1, j-1)
         print xi
      elseif b[i,j] == up
        PRINT-LCS(b, X, i-1, j)
      else PRINT-LCS(b,X, i,j-1)

#codingexercise


Double  GetNthRootProductOddRaisedPDividedQAndEvenRaisedPTimesQ (Double [] A,Double  p, Double q)


{



If ( A== null) return 0;



Return A.NthRootProductOddRaisedPDividedQAndEvenRaisedPTimesQ(p, q);



}