tooh’s diary

半角全角、常体敬体が入り乱れるカオス

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)が必要になる、みたいな。