algorithm - 切り抜かれた雑誌のキャラクターからメッセージを生成する（インタビューの質問）

Question

この問題は、 SkienaによるThe AlgorithmDeisgnManualの動的計画法の章から出てきます。

雑誌から切り抜きを貼り付けて、特定の文字列を生成できるかどうかを判断するアルゴリズムを提供します。任意の文字位置について、ページの裏側にある文字とその位置を識別する関数が与えられます。

私はこれをバックトラックで解決しましたが、動的計画法の章にあるので、私には理解できない再発があるに違いないと思います。誰かが私にヒントを与えることができますか？

Answer 1

最大の2部マッチングでそれを解くことができます。

指定された文字列の各文字Lは、左側のセットを形成します。（文字列に文字が繰り返されている場合は、文字を繰り返すことに注意してください）。

マガジンの文字の各ペア（R1、R2）は、適切なセットを形成します。

L =R1またはL=R2の場合、Lは（r1、r2）に接続されます。

結果のグラフで最大の一致を見つけます。左のすべての頂点が一致の一部である場合、答えがあります。そうでない場合、そのような文字列は使用できません。

アルゴリズムについては、最大2部マッチングを参照してください。

ただし、これが最適かどうかはわかりません。質問どおりに正確に回答できなかったことをお詫びします。

Answer 2

再帰的なバックトラッキングソリューションがある場合は、動的計画法を実行する1つの方法であるメモ化を適用できる場合があります。