Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.
Jika masalahnya berpunca daripada fakta bahawa adalah perlu untuk membahagikan tatasusunan kepada subsegmen yang tidak bersilang (urutan elemen berturut-turut) dengan cara yang optimum (atau mengira bilangan pemisahan yang sesuai), maka ia patut dicuba untuk menyelesaikannya menggunakan pengaturcaraan dinamik.
Contoh skema penyelesaian adalah seperti berikut:
dp[i] - respons untuk elemen i pertama
Mengira dp[i]: memandangkan kita hanya mempertimbangkan elemen i pertama, elemen ke-i akan menjadi yang terakhir, yang bermaksud bahawa elemen ini akan berada dalam subsegmen terakhir dan, pada masa yang sama, elemen paling kanan di sana. Oleh itu, kita boleh lelaran melepasi sempadan kiri subsegmen terakhir j. Dalam proses penghitungan, kita akan mengira nilai subsegmen ini, dan jika betul, maka kita akan mengira semula dp[i] hingga dp[j - 1] dan nilai subsegmen [j;i].
Pertimbangkan masalah mudah berikut: memandangkan tatasusunan integer, anda perlu membahagikannya kepada bilangan minimum subsegmen tidak bersilang supaya setiap nombor dimasukkan dalam beberapa subsegmen dan setiap subsegmen mengandungi nombor yang sama. Contohnya, untuk tatasusunan 1 2 2 3 3 3 2 1 1, partition optimum kelihatan seperti ini: [1] [2 2] [3 3 3] [2] [1 1]. Tugas ini mudah diselesaikan dengan hanya melalui tatasusunan (kami meletakkan semua elemen berturut-turut yang sama dalam satu subsegmen), tetapi kami akan menyelesaikannya menggunakan pengaturcaraan dinamik sebagai contoh.
intn;
cin>> n;
// isikan tatasusunan dengan 1-index
vektor arr(n + 1);
untuk (int i = 1; i <= n; i++)
cin>> arr[i];
// pada mulanya tetapkan +oo kepada nilai dp
vektor dp(n + 1, 1000000000);
// susunan panjang sifar tidak perlu dipecah, jadi jawapan untuknya ialah 0
dp[0] = 0;
// hitung jawapan untuk dp[i] dalam menaik i
untuk (int i = 1; i <= n; i++) {
// pada masa ini arr[i] ialah elemen terakhir, jadi ia akan menjadi nombor paling kanan dalam subsegmen terakhir
// gelung melalui semua pilihan untuk tempat subsegmen terakhir ini bermula
untuk (int j = i; j > 0; j--) {
jika (arr[j] != arr[i]) {
// jika anda bertemu elemen yang tidak sama dengan yang terakhir, maka subsegmen akan mengandungi nombor yang berbeza, dan ini tidak sesuai dengan syarat
// tidak ada gunanya meneruskan, kerana mengalihkan sempadan kiri ke kiri, elemen ini tidak akan hilang, jadi kita pecah
pecah;
}
// bayangkan subsegmen terakhir ialah [j;i]
// jadi anda perlu mengambil partition optimum bagi elemen j-1 pertama dan tambah 1 (subsegmen [j; i] itu sendiri)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Jika elemen mungkin tidak tergolong dalam mana-mana subsegmen, maka anda hanya perlu mempertimbangkan pilihan yang sesuai, kerana dp[i] = dp[i - 1]