免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.
配列を最適に破棄/崩壊/結合 (または同様の) する必要がある問題の場合は、サブセグメントに対する動的プログラミングを使用して問題を解決する必要があります。
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 つの部分に分割するだけでなく、任意の数の部分に分割するオプションも考慮されます。