Go语言视频零基础入门到精通

admin

1.问题描述：
　　什么是最长公共子序列呢?好比一个数列 S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S 称为已知序列的最长公共子序列。
　　举个例子，如：有两条随机序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。
　　
　　注意：【最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别】
　　子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素 而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df， 而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。下文具体描述。
2.解决思路：
2.1穷举法
　　（靠蛮力啊。。。）
2.2动态规划法
　　用动态规划法首先要判断该问题是否符合动态规划法的条件。时间复杂度O（n^2)。
　　(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
　　(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
　　(3) 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
3.源码：

1. // LCSTest.cpp : 定义控制台应用程序的入口点。  
2. #include "stdafx.h"  
3. #include<iostream>  
4. #include<cstdlib>  
5. #include<string>  
6. #include<vector>  
7. using namespace std;  
8.       
9. void LCS(string str1,string str2)  
10. {  
11.     int len1 = str1.length();  
12.     int len2 = str2.length();  
13.     //int **dp = new int[len1+1][len2+1];  
14.     vector<vector<int> > dp(len1+1,vector<int>(len2+1));  
15.          
16.     //动态规划初始值     
17.     for(int j = 0;j <= len2;j++)  
18.         dp[0][j] = 0;  
19.     for(int i = 0;i <=len1;i++)  
20.         dp[i][0] = 0;  
21.    
22.     for(int i = 0;i < len1;i++)  
23.         for(int j = 0;j < len2;j++)  
24.         {  
25.             if(str1.at(i) == str2.at(j))  
26.             {  
27.                 dp[i+1][j+1]= dp[i][j]+1;                 
28.             }  
29.             else if(dp[i][j+1] > dp[i+1][j])  
30.                 dp[i+1][j+1] = dp[i][j+1];  
31.             else   
32.                 dp[i+1][j+1] = dp[i+1][j];  
33.         }  
34.         cout<<"最长公共子序列长度为："<<dp[len1][len2]<<endl;  
35.       
36.         int ti = 0;  
37.         int tj = 0;  
38.         while(ti<len1 && tj<len2 )  
39.         {  
40.             if(str1.at(ti) == str2.at(tj))  
41.             {  
42.                 cout<<str1.at(ti)<<" ";  
43.                 ti++;  
44.                 tj++;  
45.             }  
46.             else if(dp[ti+1][tj] >= dp[ti][tj+1])  
47.                 ti++;  
48.             else  
49.                 tj++;  
50.         }  
51. }  
52. int _tmain(int argc, _TCHAR* argv[])  
53. {  
54.     string str1 = "asddgflsksdjflkdf";  
55.     string str2 = "sdflsdzf";  
56.     LCS(str1,str2);  
57.     return 0;  
58. }  

复制代码