免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.
問題が、最適な方法で交差しないサブセグメント (一連の連続した要素) に配列を分割する (または適切な分割数をカウントする) 必要があるという事実に要約される場合は、解決を試みる価値があります。動的計画法を使用します。
ソリューション スキームの例は次のとおりです。
dp[i] - 最初の i 要素に対する応答
dp[i] のカウント: 最初の i 要素のみを考慮しているため、i 番目の要素が最後の要素になります。つまり、この要素は最後のサブセグメントにあり、同時にそこの右端の要素になります。したがって、最後のサブセグメント j の左側の境界を反復処理できます。列挙の過程で、このサブセグメントの値を計算し、それが正しい場合は、dp[i] から dp[j - 1] とサブセグメントの値 [j;i] を再計算します。
次の簡単な問題を考えてみましょう: 整数の配列が与えられた場合、それを最小数の交差しないサブセグメントに分割して、各数値が何らかのサブセグメントに含まれ、各サブセグメントに同じ数値が含まれるようにする必要があります。たとえば、配列 1 2 2 3 3 3 2 1 1 の場合、最適なパーティションは [1] [2 2] [3 3 3] [2] [1 1] のようになります。このタスクは、配列を通過するだけで簡単に解決できますが (同じ連続する要素をすべて 1 つのサブセグメントに入れます)、例として動的計画法を使用して解決します。
intn;
シン>> n;
// 配列を 1 インデックスで埋めます
vector arr(n + 1);
for (int i = 1; i <= n; i++)
シン>> arr[i];
// 最初に +oo を dp 値に設定します
vector dp(n + 1, 1000000000);
// 長さゼロの配列は分割する必要がないので、答えは 0 です
dp[0] = 0;
// i の昇順で dp[i] の答えを数えます
for (int i = 1; i <= n; i++) {
// 現在 arr[i] は最後の要素であるため、最後のサブセグメントの右端の番号になります
// この最後のサブセグメントが開始された場所のすべてのオプションをループします
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// 最後の要素と等しくない要素に遭遇した場合、サブセグメントには異なる数値が含まれ、これは条件に適合しません
// 続行しても意味がないため、左の境界線を左に移動しても、この要素は消えないため、ブレークします
壊す;
}
// 最後のサブセグメントが [j;i] だったとします
// したがって、最初の j-1 要素の最適な分割を取得し、1 を追加する必要があります (サブセグメント [j; i] 自体)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
要素がどのサブセグメントにも属さない可能性がある場合は、dp[i] = dp[i - 1] のように適切なオプションを検討する必要があります。