求公共最長子序列數目，這種型別不用多想，dp就完了（自我感覺最簡單的dp）
首先確定狀態，兩串字串比較，所以用二維的dp[i][j]
然后轉移方程，當str1[i]=str2[j]時，由兩字串同時加一得到，dp[i][j]=dp[i-1][j-1]+1;
當str1[i]!=str2[j]時，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
當然需要定義邊界條件，比如：i=0或j=0時，dp[0][j]或dp[i][0]=0;
按從小到大的順序遍歷就完了，時間復雜度O(n^2);
然后如果要輸出最長公共子序列的時候就倒退，原理懂了很簡單（這部分代碼注釋是掉的）
下面是代碼：
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string str1,str2;
while(cin>>str1>>str2){
//cin >> str1 >> str2;
int x1=str1.size(),x2=str2.size(),i,j;
vector<int>vec(x1+1,0);
vector<vector<int> > vec1(x2+1,vec);
for(i=0;i<x2;i++){//str2
for(j=0;j<x1;j++){//str1
if(str1[j]==str2[i])vec1[i+1][j+1]=vec1[i][j]+1;
else if(vec1[i+1][j]>vec1[i][j+1])vec1[i+1][j+1]=vec1[i+1][j];
else vec1[i+1][j+1]=vec1[i][j+1];
}
}
cout << vec1[i][j] << endl;
/*
int k=0;
while(i>0&&j>0)
if(vec1[i][j]==vec1[i-1][j])i--;
else if(vec1[i][j]==vec1[i][j-1])j--;
else{
i--,j--;
vec[k++]=j;
}
for(i=k-1;i>=0;i--){
cout << str1[vec[i]];
}
cout << endl;
*/
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67313.html
標籤：C++
上一篇：pearls
下一篇：C#排序案例