動的計画法(DP)の実装の考え方について

Question

現状

動的計画法の実装を、競技プログラミングの例題を通して勉強しています。
F-LCS
動的計画法の考え方は理解したものの、実際に問題に当てはめるとなるとなかなか方針が立ちません。
上記リンクの問題に動的計画法を無視して考えたコードは以下のようなものです。

import itertools
s,t=str(input()),str(input())
x=set("".join(x) for i in range(1,len(s)+1) for x in itertools.combinations(s,i))
y=set("".join(x) for i in range(1,len(s)+1) for x in itertools.combinations(t,i))
z=list(x&y)
l=list(map(len,z))
idx=l.index(max(l))
print(z[idx])

一方で、動的計画法による解答例は以下のようなものです。

from subprocess import*
call(('pypy3','-c',"""
s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])
ans=""
i,j=n,m
while 0<i and 0<j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans+=s[i-1]
        i-=1
        j-=1
 
print(ans[::-1])
"""))

分からないこと

ナップサック問題などでは、何をメモ化しているのかが理解できるのですが、今回の問題ではいまいち理解できません。上記の解答例のコードでは、何をdpに記録して進めているのか教えていただきたく思います。

Answer 1

これは共通部分文字列の最大長を求めた後、その文字列を復元するっていう二つのステップからなってます。
最大長を求めるステップでは、DP[i][j]に「文字列Sの0〜i-1文字目までと、文字列Tの0〜j-1文字目までを使ったときの共通部分文字列の最大長」が入るようにDP表を更新してます。

類似の典型アルゴリズムに「編集距離」というのがありまして、これで検索すると分かりやすい解説が出てくると思うので、調べてみてください。

Comments

[退会済みユーザー]

通常のナップサック問題と違って、DPテーブルから直接答えが求まらないことが理解につながらない原因でした。編集距離の考え方を知った今では、上記のコードの意味も分かるようになりました。
さらに、DPテーブルの最大値から文字列を復元するステップもこの問題の肝となっているようですね。
ご回答ありがとうございました。
詳しい解説ページがあったので、メモとして残しておきます。
https://qiita.com/drken/items/03c7db44ccd27820ea0d