[BOJ 9251] LCS(Python)

5557 ワード
DP boj テキストリンク
質問する
LCS
問題の説明
ACAYKP
CAPCAK
2つの文字列の最長共通部スコアの問題を検索します.
A
C
長さ:0
A
CA
長さ:1(A)
A
CAP
長さ:1(A)
....
AC
C
長さ:1(C)
AC
CA
長さ:1(C)
AC
CAPC
長さ:2(AC)
このように完全ナビゲーションを行い、DPを充填すればよい.
DPを充填する方法は、最後の文字と同時に長さが増加することを保証するために、このように追加される.各文字列には、文字の前の最大長+1が含まれます.
最後の文字が異なる場合は、
AC
CAPCA
A
CAPCA
AC
CAPC
どちらの場合も、より長い長さを選択できます.
点火式.
行列[i][j]=matrix[i-1][j-1]+1(文字が同じ場合)
行列[i][j]=max(行列[i][j-1]、行列[i-1][j])(文字が異なる場合)
すべてのDPが入力されている場合、各文字列状態の共通部の点数が最も長い.
プールコード
str1 = input()
str2 = input()

dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
for i in range(len(str1)):
    for j in range(len(str2)):
        # 탐색 시 서로 같은 문자가 추가 된다면
        if str1[i] == str2[j]:
            # 같은 문자가 추가 되기 전 가장 긴 문자열 + 1
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            # 같은 문자가 아니면 str1, str2에서 문자 하나 뺀 것
            # str2, str1에서 문자 하나 뺀 것과 비교 후 큰 값 삽입
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
print(dp[len(str1)][len(str2)])
Githubアクション環境変数と文脈についての4つのチップス
Android開発学習ノート(8):Handlerがマルチスレッドと非同期処理を実現