. Pencetak Pelik

664. Pencetak Pelik

Kesukaran: Sukar

Topik: Rentetan, Pengaturcaraan Dinamik

Terdapat pencetak pelik dengan dua sifat istimewa berikut:

• Pencetak hanya boleh mencetak urutan aksara yang sama setiap kali.
• Pada setiap giliran, pencetak boleh mencetak aksara baharu bermula dari dan berakhir di mana-mana tempat dan akan meliputi aksara sedia ada asal.

Memandangkan rentetan s, kembalikan bilangan pusingan minimum yang diperlukan oleh pencetak untuk mencetaknya.

Contoh 1:

• Input: s = "aaabbb"
• Output: 2
• Penjelasan: Cetak "aaa" dahulu dan kemudian cetak "bbb".

Contoh 2:

• Input: s = "aba"
• Output: 2
• Penjelasan: Cetak "aaa" dahulu dan kemudian cetak "b" dari tempat kedua rentetan, yang akan meliputi aksara 'a' sedia ada.

Kekangan:

• 1 <= s.panjang <= 100
• s terdiri daripada huruf kecil Inggeris.

Penyelesaian:

Kita boleh menggunakan pengaturcaraan dinamik. Ideanya adalah untuk meminimumkan bilangan lilitan yang diperlukan untuk mencetak rentetan dengan memecahkannya kepada submasalah.

Masalah boleh diselesaikan menggunakan pengaturcaraan dinamik. Ideanya adalah untuk membahagikan masalah kepada submasalah yang lebih kecil di mana anda menentukan pusingan minimum yang diperlukan untuk mencetak setiap subrentetan s. Kita boleh memanfaatkan pemerhatian berikut:

• Jika dua aksara bersebelahan adalah sama, anda boleh melanjutkan operasi sebelumnya dan bukannya mengiranya sebagai operasi baharu.

Penyelesaian Pengaturcaraan Dinamik

Biar dp[i][j] ialah bilangan lilitan minimum yang diperlukan untuk mencetak subrentetan s[i:j+1].

1. Jika s[i] == s[j], maka dp[i][j] = dp[i][j-1] kerana aksara terakhir s[j] boleh dicetak dengan operasi sebelumnya.
2. Jika tidak, dp[i][j] = min(dp[i][k] + dp[k+1][j]) untuk semua i <= k < j.

Mari laksanakan penyelesaian ini dalam PHP: 664. Pencetak Pelik

  
  
  Penjelasan:



Susunatur DP: Tatasusunan 2D dp[i][j] mewakili bilangan lilitan minimum yang diperlukan untuk mencetak subrentetan daripada indeks i ke j.
Permulaan: Kami memulakan dp[i][i] = 1 kerana satu aksara boleh dicetak dalam satu pusingan.

Mengisi Jadual DP:


Jika aksara pada i dan j adalah sama ($s[$i] == $s[$j]), maka cetakan dari i ke j mengambil bilangan lilitan yang sama seperti mencetak dari i ke j-1 memandangkan $s[$j] ​​boleh dicetak dalam giliran yang sama seperti $s[$i].
Jika ia berbeza, kami cuba mencari bilangan lilitan minimum dengan membahagikan rentetan pada titik yang berbeza (k).


Hasil: Bilangan lilitan minimum yang diperlukan untuk mencetak keseluruhan rentetan disimpan dalam dp[0][$n - 1].


Penyelesaian ini dengan cekap mengira bilangan lilitan minimum yang diperlukan untuk mencetak rentetan dengan mempertimbangkan semua cara yang mungkin untuk membelah dan mencetak rentetan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Pencetak Pelik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!