9251号:LCS

907 ワード
python テキストリンク 
import sys
input = sys.stdin.readline

words = []

for _ in range(2):
  words.append(list(map(str,input().rstrip())))

a = len(words[0])
b = len(words[1])

dp = [[0]*(b+1) for _ in range(a+1)]

for i in range(1,a+1):
  for j in range(1,b+1):
    if words[0][i-1] == words[1][j-1]:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])

print(dp[a][b])
これは動的計画法の最も基本的なものであり、代表的な問題の最長の公共部分数列でもある.
まず、rstripを使用してリスト単語の2つの文字列を受け入れます.
次に、2つの単語の文字列長をa,bに入れ、リストdpに(b+1)個の0のリスト(a+1)を作成する.
このようにしてリストを作成する場合、dpリストのリスト要素の0を2つの繰り返し文ですべて共通部分数列に設定できます.
2つの重複文でif文を使用し、単語の0番目のインデックスのi-1と1番目のインデックスのj-1が同じである場合、
dp[i][j] = dp[i-1][j-1] + 1
つまり、前の最高値に+1を加えればいいのです.
Elseはdp[i][j]=max(dp[i][j-1],dp[i-1][j])により値を付与する.
最後の値dp[a][b]を出力すれば、最低価格が得られる.
[アルゴリズム]白駿Python 1475102
プログラマ-Java付きディスクコントローラ