最長共同子序列 (Longest Common Subsequence)

題目

輸入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)