題目
輸入2個英文字串,輸出最長共同子序列的長度。(可以跳過字元,但順序不能改變)
範例:輸入 comp 和 zope,答案是 2。(o和p)
解法
如果 s1 第 i 個字元等於 s2 第 j 個字元,就 +1。
即 dp[i][j] = dp[i-1][j-1] + 1;
否則 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
程式碼
#include <bits/stdc++.h>
using namespace std;
int main(){
string s1, s2;
cin >> s1 >> s2;
int dp[s1.length()][s2.length()];
memset(dp, 0, sizeof(dp));
for(int i=1; i<s1.length(); i++){
for(int j=1; j<s2.length(); j++){
if(s1[i] == s2[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout << dp[s1.length()-1][s2.length()-1] << '\n';
}
時間複雜度:O(s1len*s2len)