CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

問題原文

atcoder.jp

解法

２つの文字列 と があったとして、削除のみを用いて にする場合、 と の最長共通部分列を残すのが最適。
よって をどこかで二分し、それらを , として最長共通部分列長を計算すればよい。
全ての切り分け方を試して、最小値が答え。

実装

N = int(input())
S = input()

ans = float('inf')
for m in range(N + 1):
    L, R = S[:m], S[m:]
    dp = [[0] * (len(R) + 1) for _ in range(len(L) + 1)]
    for l, ls in enumerate(L, start=1):
        for r, rs in enumerate(R, start=1):
            if ls == rs:
                dp[l][r] = dp[l - 1][r - 1] + 1
            else:
                dp[l][r] = max(dp[l - 1][r], dp[l][r - 1])
    ans = min(ans, N - 2 * dp[-1][-1])

print(ans)

感想

えっ、難しかったえっ
個人的には次の一次元オセロの倍ぐらい難しかったです。。。解けてよかった