10405 Longest Common Subsequence

解題思路

使用 LCS 算法

程式碼

#include <iostream>
using namespace std;

int main() {
    string a, b;
    while (getline(cin, a) && getline(cin, b)) {
        int dp[a.length() + 1][b.length() + 1];
        for (int i = 0; i <= a.length(); i++) dp[i][0] = 0;
        for (int i = 0; i <= b.length(); i++) dp[0][i] = 0;
        for (int i = 1; i <= a.length(); i++)
            for (int j = 1; j <= b.length(); j++) {
                if (a[i - 1] != b[j - 1])
                    dp[i][j] =
                        max(max(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);
                else
                    dp[i][j] = dp[i - 1][j - 1] + 1;
            }
        cout << dp[a.length()][b.length()] << endl;
    }
}