質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

3435閲覧

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

退会済みユーザー

退会済みユーザー

総合スコア0

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2020/02/06 07:28

現状

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

Python

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

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

pypy3

1from subprocess import* 2call(('pypy3','-c',""" 3s=input() 4t=input() 5n,m=len(s),len(t) 6dp=[[0]*(m+1) for i in range(n+1)] 7dp[0][0]=1 8for i in range(n+1): 9 for j in range(m+1): 10 dp[i][j]=max(dp[i][j-1],dp[i-1][j]) 11 if i*j!=0 and s[i-1]==t[j-1]: 12 dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]) 13ans="" 14i,j=n,m 15while 0<i and 0<j: 16 if dp[i][j]==dp[i-1][j]: 17 i-=1 18 elif dp[i][j]==dp[i][j-1]: 19 j-=1 20 else: 21 ans+=s[i-1] 22 i-=1 23 j-=1 24 25print(ans[::-1]) 26"""))

分からないこと

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

投稿2020/02/06 07:53

編集2020/02/06 07:58
set0gut1

総合スコア2413

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2020/02/06 17:03

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問