Baekjoon 9251.py [LCS]

6754 ワード
DP テキストリンク
もし問題があったら?

説明する

import sys
input = sys.stdin.readline

w1 = input().rstrip()
w2 = input().rstrip()
lenOfw1 = len(w1)
lenOfw2 = len(w2)
dp = [[0]*(lenOfw2+2) for _ in range(lenOfw1+2)]
result = 0

for i in range(2, lenOfw1+2):
    for j in range(2, lenOfw2+2):
        dp[i-1][j-1] = max(dp[i-2][j-2], dp[i-1][j-2], dp[i-2][j-1], dp[i-1][j-1])
        if w1[i-2] == w2[j-2]:
            dp[i][j] = dp[i-1][j-1] + 1
            result = max(dp[i][j], result)
print(result)

ふくガス


今の文字が同じなら、すぐに昔のdp + 1の論理を思い出しました.しかし、以前の文字ではなく、以前の文字に同じ文字がある場合は、当時のdp + 1を現在のdpに保存するので、この方法を実現するには長い時間がかかる.

疑問符位置には、赤い四角形の最大値+1が含まれます.dp[i-1][j-1] = max(dp[i-2][j-2], dp[i-1][j-2], dp[i-2][j-1], dp[i-1][j-1])として保存されます.
これを使用すると、indexは0,0から常にdp[i-1][j-1]に最値を格納しているため、現在dp[i][j] = dp[i-1][j-1]+1は最値のみを格納している.
Many-to-many
[Hip]デュプレステージキュー