Python3でまったり競技プログラミング 2日目（DP）

はわわ〜〜〜〜〜〜〜〜。

今日はDP。

Edit Distance (Levenshtein Distance) | Aizu Online Judge

レーベンシュタイン距離（編集距離）は何回の操作である文字列を別の文字列に変形できるか、を表したもの。
qiita.com
詳しい説明と実装方法は上に載ってる。

s = input()
t = input()
w = len(s)+1
h = len(t)+1
dp = []
for i in range(h):
    L = [0]*w
    dp.append(L)
for i in range(w):
    dp[0][i] = i
for i in range(h):
    dp[i][0] = i
for i in range(h-1):
    for j in range(w-1):
        if t[i] == s[j]:
            dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1)
        else:
            dp[i+1][j+1] = min(dp[i][j]+1,dp[i][j+1]+1,dp[i+1][j]+1)
print(dp[h-1][w-1])

最長増加部分列 | 動的計画法 | Aizu Online Judge

最長部分増加列(LIS)の問題。いつかに解説を書いてたのでそれ参照。

C - BBuBBBlesort!

DPじゃないけど。
n個の数字を与えられるので、それを座標圧縮（大小関係を保ったまま0~n-1に直す）して、偶奇が同じであれば1つ飛ばしのソートで適切な場所に戻せるので、偶奇が異なる部分がいくつあるかを数えればいい。

例えば、
1 3 2 4 5 7 6
は、
1 2 3 4 5 6 7
と4箇所違うので、2回の入れ替え（4÷2）が必要になる、みたいな。