首页 > 代码库 > 动态规划二：最长公共子序列（LCS）
动态规划二：最长公共子序列（LCS）
1.两个子序列：X={x1,x2....xm}，Y={y1,y2....yn}，设Z={z1,z2...zk}。
2.最优子结构：
1）如果xm=yn ，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS。
2）如果xm!=yn ，则zk!=xm包含Z是Xm-1和Y的一个LCS。
3）如果xm!=yn ，则zk!=yn包含Z是X和Yn-1的一个LCS。
3.则由最优子结构可得递归式：
4.实现：
1 #include<string> 2 #include<iostream> 3 using namespace std; 4 5 int arr[20][20] = {}; 6 void LCS(string str1, string str2){ 7 int len1 = str1.length(); 8 int len2 = str2.length(); 9 //边界10 for (int i = 0; i <= len1; i++)11 arr[i][0] = 0;12 for (int j = 0; j <= len2; j++)13 arr[0][j] = 0;14 //检验15 for (int i = 1; i <= len1; i++)16 {17 for (int j = 1; j <= len2; j++)18 {19 if (str1[i - 1] == str2[j - 1]) //记录20 {21 arr[i][j] = arr[i - 1][j - 1] + 1;22 }23 else if (arr[i][j - 1] >= arr[i - 1][j])24 {25 arr[i][j] = arr[i][j - 1];26 }27 else 28 {29 arr[i][j] = arr[i - 1][j];30 }31 }32 }33 }34 35 void printLCS(string str1, string str2,int len1, int len2){36 cout << "最长公共子序列长为：" << arr[len1][len2] << endl;37 //倒序输出38 while (len1&&len2){39 if (str1[len1-1]==str2[len2-1])40 {41 cout << str1[len1 - 1];42 len1--;43 len2--;44 }45 else if (arr[len1][len2-1]>=arr[len1-1][len2])46 {47 len2--;48 }49 else{50 len1--;51 }52 }53 cout << endl;54 }55 56 int main()57 {58 string str1 = "abcdsnnnn";59 string str2 = "acbdanm";60 LCS(str1, str2);61 printLCS(str1, str2,str1.length(), str2.length());62 return 0;63 }
动态规划二：最长公共子序列（LCS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。