首页 > 代码库 > 最长公共子序列的代码实现
最长公共子序列的代码实现
关于最长公共子序列（LCS）的相关知识，http://blog.csdn.net/liufeng_king/article/details/8500084 这篇文章讲的比较好，在此暂时不再详说。
以下是我代码实现两种方式：递归+递推：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int A[100]; 4 int B[100]; 5 6 //int B[]={2,3,5,6,9,8,4}; 7 int d[100][100]={0}; 8 int dp(int i, int j,vector<int> &vs){ 9 int &ans = d[i][j];10 if(ans > 0)return ans;11 if(i>0&&j>0){12 if(A[i] == B[j]){13 ans = dp(i-1,j-1)+1;14 } 15 else ans = max(dp(i-1,j),dp(i,j-1));16 }17 else{18 ans = 0;19 }20 return ans;21 }22 int LCS(int n1, int n2){23 for(int i = 0; i <= n1; i++)d[i][0] = 0;24 for(int i = 0; i <= n2; i++)d[0][i] = 0; 25 for(int i = 1; i<= n1; i++){26 for(int j = 1; j<= n2; j++){27 if(A[i]==B[j]){28 d[i][j] = d[i-1][j-1]+1;29 }30 else d[i][j] = max(d[i-1][j], d[i][j-1]);31 }32 }33 return d[n1][n2];34 }35 int main(){36 int n1,n2 ;37 cin >> n1;38 for(int i = 1;i <= n1; i++) cin >> A[i];39 cin >> n2;40 for(int i = 1;i <= n2; i++) cin >> B[i];41 memset(d,-1,sizeof(d));42 d[0][0] = 0;43 vector<int> vs;44 cout << dp(n1,n2,vs) << endl;45 cout << LCS(n1 ,n2) << endl;46 //cout << dp(5,6) << endl;47 48 return 0;49 }
最长公共子序列的代码实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。