20. Dynamic Programming 3

Longest Common Subsequence(LCS) Problem

1. what is the subsequence:
   ⟨A2,C3,B4,B7,C8,W11⟩ is a subsequence of ⟨T,A,C,B,B,W,B,C,W,T,W⟩.

2. Given two sequences X and Y , a sequence Z is called the common subsequence of X and Y if Z is a subsequence of both X and Y.

3. The longest-common-subsequence problem is to find a common subsequence Z = LCS(X,Y) with the maximum length from both sequences X andY.

Denote by
Xm = ⟨x1,x2,...,xm⟩
Yn = ⟨y1,y2,...,yn⟩
Our task then is to find an LCS(Xm,Yn) of Xm and Yn.

Solution

1. Characterize the structure of an optimal solution (the key observation)

   
   

2. Recurrence of the optimal solution

Smart Use of the LCS algorithm

Question: Given a sequence of n elements, the problem is to find a longest increasing (or decreasing) subsequence of the sequence.

Answer:
Let X be the original sequence and Y the sorted sequence of X in increasing order. Then, the longest increasing subsequence of X is LCS(X,Y)

Question 2: given three sequences X , Y and Z with length nX , nY and nZ , respectively, find a longest common subsequence W among the three sequences, what is the running time of the proposed algorithm?

The crucial thing of the algorithm is to find the dependency of the subproblem and main problem

Question 3: 最长回文字符串

1. When the question is asking whether the result is correct，the easiest thing is to find a counterexample and prove it false。
2. For DP, the time complexity is O(n), n is the input number rather than the size of input.
3. the most important part of DP is the storing slots(one dimension or two) and optimal substructure.
4. to deal with the DP, make sure the aim, the transfer function(how to divide huge to small questions) and the small questions are also the same question to original question, the only difference is the size or scale of the problem.
5. sometimes for different condition, the transfer function is different.