Kira Cara Untuk Membina Rentetan Yang Baik

2466. Kira Cara Untuk Membina Rentetan Yang Baik

Kesukaran: Sederhana

Topik: Pengaturcaraan Dinamik

Memandangkan integer sifar, satu, rendah dan tinggi, kita boleh membina rentetan dengan bermula dengan rentetan kosong, dan kemudian pada setiap langkah melakukan salah satu daripada yang berikut:

• Tambahkan aksara '0' sifar kali.
• Tambahkan aksara '1' sekali.

Ini boleh dilakukan beberapa kali.

Rentetan baik ialah rentetan yang dibina oleh proses di atas yang mempunyai panjang antara rendah dan tinggi (inklusif).

Kembalikan bilangan berbeza rentetan baik yang boleh dibina memenuhi sifat ini. Oleh kerana jawapannya boleh besar, kembalikan modulo 10⁹ 7.

Contoh 1:

• Input: rendah = 3, tinggi = 3, sifar = 1, satu = 1
• Output: 8
• Penjelasan:
  • Satu kemungkinan rentetan baik yang sah ialah "011".
  • Ia boleh dibina seperti berikut: "" -> "0" -> "01" -> "011".
  • Semua rentetan binari daripada "000" hingga "111" ialah rentetan yang baik dalam contoh ini.

Contoh 2:

• Input: rendah = 2, tinggi = 3, sifar = 1, satu = 2
• Output: 5
• Penjelasan: Rentetan yang baik ialah "00", "11", "000", "110" dan "011".

Kekangan:

• 1 <= rendah <= tinggi <= 10⁵
• 1 <= sifar, satu <= rendah

Petunjuk:

1. Kira bilangan rentetan yang baik dengan panjang kurang atau sama dengan beberapa pemalar x.
2. Gunakan pengaturcaraan dinamik menggunakan saiz kumpulan sifar dan satu berturut-turut.

Penyelesaian:

Kita perlu menumpukan pada membina rentetan dengan panjang yang berbeza dan mengira bilangan rentetan yang sah yang memenuhi syarat yang diberikan. Mari kita pecahkan pendekatan:

Pecahan Masalah

1. Definisi Negeri:
   Biarkan dp[i] mewakili bilangan rentetan panjang i yang sah yang boleh dibina menggunakan nilai sifar dan satu yang disediakan.

2. Hubungan Berulang:

   • Dari sebarang panjang i, kita boleh tambahkan sama ada:
     • sifar 0s berturut-turut, jadi rentetan sebelumnya adalah panjang i-sifar, dan kami akan menambah dp[i-sifar] cara.
     • satu 1s berturut-turut, jadi rentetan sebelumnya adalah panjang i-one, dan kami akan menambah cara dp[i-one].

Hubungan berulang menjadi:
dp[i] = dp[i - sifar] dpi - satu

1. Kes Asas:

   • Terdapat satu cara untuk membina rentetan kosong: dp[0] = 1.

2. Pengiraan Akhir:

   • Jumlah bilangan rentetan panjang yang sah antara rendah dan tinggi ialah jumlah dp[i] untuk semua i dari rendah ke tinggi.

Langkah Penyelesaian

1. Mulakan tatasusunan dp bersaiz tinggi 1 di mana setiap indeks i mewakili bilangan rentetan panjang i yang sah.
2. Gelung melalui setiap kemungkinan panjang i dari 1 hingga tinggi, mengemas kini dp[i] berdasarkan hubungan ulangan.
3. Hitung jumlah dp[i] dari rendah ke tinggi untuk mendapatkan keputusan akhir.

Mari laksanakan penyelesaian ini dalam PHP: 2466. Kira Cara Untuk Membina Rentetan Yang Baik

  
  
  Penjelasan:




Permulaan: Kita mulakan dengan menetapkan huruf besar dp[0] = 1, bermakna terdapat satu cara untuk membentuk rentetan panjang 0 (rentetan kosong).

Kemas Kini Pengaturcaraan Dinamik: Untuk setiap kemungkinan panjang rentetan i dari 1 hingga tinggi, kami menyemak sama ada kami boleh menambah rentetan panjang sifar atau satu pada rentetan yang lebih kecil. Kami mengemas kini dp[i] sewajarnya dengan menambah bilangan cara untuk membentuk rentetan panjang i-sifar dan i-satu, memastikan bahawa keputusan diambil modulo 109 7.

Pengiraan Keputusan Akhir: Kami meringkaskan semua nilai dp[i] untuk i dalam julat [rendah, tinggi] untuk mendapatkan kiraan akhir rentetan yang sah.



  
  
  Kerumitan Masa:



Mengisi tatasusunan dp mengambil masa O(tinggi).
Menjumlahkan hasil yang sah antara rendah dan tinggi mengambil O(tinggi - rendah 1).


Oleh itu, kerumitan masa keseluruhan ialah ** O(tinggi) **, yang cukup cekap untuk had input.


  
  
  Kerumitan Ruang:



Kami menggunakan dp tatasusunan bersaiz tinggi 1, jadi kerumitan ruang adalah O(tinggi).


Penyelesaian ini menyelesaikan masalah dalam kekangan dengan cekap.

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 Kira Cara Untuk Membina Rentetan Yang Baik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!