動的プログラミングのパターン - 2

免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.

配列を最適に破棄/崩壊/結合 (または同様の) する必要がある問題の場合は、サブセグメントに対する動的プログラミングを使用して問題を解決する必要があります。

dp[l][r] を取得しましょう。これは、l から r までのインデックスを持つサブセグメントの最適解です。ダイナミクスの再計算はタスクに大きく依存しますが、次のような一般的な考え方があります。

1) 極端な要素 l と r を見てください。それらが他の方法で一致または補完する場合、dp[l+1][r-1] を介して dp[l][r] の値を更新できる可能性が高くなります。それ以外の場合は、dp[l][r-1] または dp[l+1[r] 経由で。

2) セグメント [l;r] が単一の構造では表現できないことがよくあります。次に、このサブセグメントの考えられるすべてのセクションを 2 つの部分に分けて検討する必要があります。つまり、要素 k を l から r-1 まで繰り返し、dp[l][r] から dp[l][k] および dp[ を再計算します。 k+1][r] 。より小さなサブセグメントでは、これらのセクションも整理されているため、実際には、サブセグメント [l;r] を 2 つの部分に分割するだけでなく、任意の数の部分に分割するオプションも考慮されます。
 

免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.

問題内の順列の存在を確認する必要がある場合、または一致する順列の数を見つける必要がある場合、または同様のものを見つける必要がある場合は、動的サブセット プログラミングの使用を検討する必要があります。

メインパラメータはビットマスクで、どの要素がすでに置換に含まれているか、どの要素が含まれていないかを示します。また、どの要素が最後に含まれたかを示す 2 番目のパラメータも必要になることがよくあります。

多くの場合、グラフ内のパスのコンテキストで順列が見られます。したがって、古典的な例であるハミルトン経路問題を考えてみましょう。
ハミルトニアン パスは、グラフの各頂点を 1 回だけ通過する単純なパスです。これは、単純に長さ n の順列として表すことができます (n は頂点の数です)。この順列内の順序は、このパス内の頂点が通過する順序を示します。

グラフ内のハミルトニアン パスの存在を確認するために、ダイナミクス dp[mask][last] を開始しましょう。マスク ビットマスクで 1 でマークされた頂点をバイパスし、最後の頂点に到達する単純なパスはありますか。
初期値は dp[2ⁱ][i] = true、残りは false になります。これは、いずれかの頂点から始まる空のパスが常に存在することを意味します。
dp[mask][last] の値を true にすると、「パスを延長する」という意味で、前方に遷移します。つまり、マスク内でゼロのマークが付いている頂点の数 (途中でまだ訪問していません) を探し、同時に最後の頂点からこの頂点までのエッジが存在する頂点の数を探します (パスは既存のエッジによって延長されます)。つまり、 dp[mask | 2^k][k] = dp[mask][last] = true かつマスク & の場合は true 2^k = 0 (頂点 k はまだ訪問されていません) そして最後にエッジがあります ->き
最終的に、オール 1 ビットマスクおよび任意の最後の頂点のパラメーターの dp に真の値があれば、ハミルトニアン パスが存在します。