標準9251 LCS

白駿9251号LCS問題.
https://www.acmicpc.net/problem/9251

草を切る

first = list(input())
second = list(input())

def lcs(first, second):
  n = len(first)
  m = len(second)
  lcs_table = [[0 for _ in range(n+1)] for _ in range(m+1)]
  for i in range(m):
    for v in range(n):
      if first[v] == second[i]:
        lcs_table[i+1][v+1] = lcs_table[i][v] + 1
      else:
        lcs_table[i+1][v+1] = max(lcs_table[i+1][v], lcs_table[i][v+1])

  return lcs_table[m][n]

print(lcs(first, second))

LCSアルゴリズム&ダイナミックプログラミング
この問題はLCSアルゴリズムを用いて解決した問題である.LCSは動的プログラミングアルゴリズムに由来し,中間計算を格納する方式である.
動的プログラミングアルゴリズムが直感的に理解しにくい場合がよくありますが、この問題はそうです.
2つの文字列を比較する場合は、dpテーブルを作成し、文字列を徐々に増やしてすべて比較する必要があります.この場合、すべてを一つ一つ比較して計算するのに時間がかかります.
したがって、各文字を比較しながら、比較後の値を保存します.次のアルファベットを計算するときは、これまでに適用されたアルファベット値をdpテーブルから取り出し、現在のアルファベットと比較することができます.
文字列の例は次のとおりです.
ACAYKP ---- 1th
CAPCAK ---- 2th
はい.
もとは正しい計算だった.

ACAYKPとCAPCAK部分数列の最長長を求める.

->ACAYKPとCAPCAの部分数列の最長長さは、最後の「P」だけを考えてもいいでしょうか?
->CAPC,CAP,CA,Cの順に下がり,各年後を求めて最終的な問題解決に用いても構わない.
->ダイナミックプログラミングを使う理由!!
アルゴリズム#アルゴリズム#

2 thの「C」を1 thの各部分数列と比較し,最長長を求めてdpテーブルに保存する.

「CA」を1 thの各部分の数列と比較し、dpテーブルの「C」結果を利用する.
「CA」の最長距離=と「C」の結果+と「A」の結果
dpテーブルに保存します.

以下のように順次行い,最終dpテーブルの最後の数字はACAYKPとCAPCAKの部分数列の最長長の解答である.