OJ Course Longest Common Subsequence

うるせぇよな。普通に。俺は好きなことを勉強したい。(仲間内のオタク構文) えぬわいです。

qiita.com

続き。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp

言わずもしれたLCS。

再帰から導いてできるかもと思ったらできなかった。

自分で考えて、漸化式を立ててみた。少し違ってて、ダメだった。惜しいね。もうちょっとDPテーブルの考察が必要だったかも。

蟻本見た。

python で書いた。

落ちた。

c++ で書いた。

通った。南無。

n = int(input())
for i in range(n):
    a = input()
    b = input()

    dp = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]

    for i in range(len(a)):
        for j in range(len(b)):
            if a[i] == b[j]:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j]+1)
            else:
                # ミス dp[i+1][j+1] = max(dp[i+1][j], dp[i][j])
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    print(dp[len(a)][len(b)])

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][1001];

int main() {
    int n;
    cin >> n;
    for (int k = 0; k < n; k++ ) {
        string a, b;
        cin >> a >> b;
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++ ) {
                if (a[i] == b[j]) {
                    dp[i+1][j+1] = dp[i][j]+1;
                } else {
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        cout << dp[a.size()][b.size()] << endl;;
    }
    return 0;
}