最長公共子序列 (LCS)：動態規劃 O(n²) 經典算法

問題描述

給定兩個長度 <100 的字符串，求最長公共子序列長度。子序列字符順序保持，不必連續。

DP 定義與轉移

dp[i][j] = 前 i 字符和前 j 字符的 LCS 長度。
if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

代碼實現

#include 
#include 
using namespace std;
int main() {
    string a, b;
    while (cin >> a >> b) {
        int n = a.size(), m = b.size();
        static int dp[200][200] = {};
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        cout << dp[n][m] << endl;
    }
}

空間優化

只需兩行滾動數組 dp[2][m+1]，或一行逆序更新（需臨時變量保存左上角值）。

輸出具體 LCS

從 dp[n][m] 回溯：若 a[i-1]==b[j-1] 則該字符屬於 LCS，移至 (i-1,j-1)；否則向值大的方向移動。