最长公共子序列求解

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的最优子结构性质，可以建立子问题最优的递归关系。用c[i][j]记录序列Xi和Yi的最长公共子序列的长度-Solving the longest common subsequence for a given sequence of sub-sequence is the sequence obtained by deleting a number of elements in the sequence. Given two sequences X and Y, while another sequence Z is X, Y promoter sequence is a sub-sequence, said sequence of X and Y Z is the common subsequence. Longest common subsequence is the sequence of the given one of the two longest common subsequence. Dynamic programming can effectively solve this problem. Longest common subsequence problem by the sub-optimal sequence of sub-structural nature of the problem can create sub-optimal recursive relationship. With c [i] [j] records series Xi and Yi, the length of the longest common subsequence