algorithm - 組み合わせ論または別のアプローチ？

Question

私は最近この問題を読みました。最初に、組み合わせアプローチを考えましたが、競技者に沿って誰もそのような解決策を提出していないようです。組み合わせ論を使用したソリューションは可能ですか? そうでない場合、解決策は何ですか？簡単に言えば、問題は次のとおりです。任意の 2 つの単語が結合され、いくつかの文字が互いに重なる可能性がある M 単語の辞書が与えられた場合、辞書から長さ N の文字列をいくつ作成できるかを見つけます。組み合わせアプローチには M! の下限があるため、連続する 2 つの単語ごとに、それらの交差を試みる必要があります。それが私が考えたものです。私はそれがうまくいくとは思わない。助けてください？

Answer 1

組み合わせ論とブルート フォースを混同しないでください。これは明らかに組み合わせカウントの問題ですが、制限時間により力ずくで解決することもできません。

これは動的計画法で解決できると思います。たとえば、部分文字列が「CAT and TCAT」で、サイズ 100 の単語をカバーする必要があるとします。

「CAT」で始まる場合は残り 97 文字、「TCAT」で始まる場合は残り 96 文字です。

したがって、f(n) がサイズ n のマッチングの解の数である場合、f(100) = f(97) + f(96) となります。

ただし、これは明らかに単純すぎて十分ではないことに注意してください。文字列が重複するケースもカバーし、同じ解を 2 回カウントしないようにする必要があります。

Answer 2

オーバーラップを無視すると、これはサブセット和問題です。オーバーラップを考慮して、オーバーラップする組み合わせをそれらの連結で置き換えると、オーバーラップの可能性がない単語のセットを取得し、その後、文字列をそれらの長さで置き換えて、合計を求めたい場合Nに、それはまさにサブセット和問題です。