最長共通部分列問題

問題

// 入力
string S1, T1;

// DP テーブル
int dp[1010][1010]; //[S : i番目][T : j番目]

int main() {
    cin >> S1 >> T1; //文字列

    memset(dp, 0, sizeof(dp)); // 初期化
    for (int i = 0; i < S1.size(); ++i) {
        for (int j = 0; j < T1.size(); ++j) {
            if (S1[i] == T1[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1); //一致すれば
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j]); //一致しなければ
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1]); //一致しなければ
        }
    }

    cout << dp[S1.size()][T1.size()] << endl; //0が初期値なので
}