. eys Papan Kekunci

650. Papan Kekunci 2 Kekunci

Kesukaran: Sederhana

Topik: Matematik, Pengaturcaraan Dinamik

Hanya terdapat satu aksara 'A' pada skrin pad nota. Anda boleh melakukan satu daripada dua operasi pada pad nota ini untuk setiap langkah:

• Salin Semua: Anda boleh menyalin semua aksara yang terdapat pada skrin (salinan separa tidak dibenarkan).
• Tampal: Anda boleh menampal aksara yang disalin kali terakhir.

Diberikan integer n, kembalikan bilangan minimum operasi untuk mendapatkan aksara 'A' tepat n kali pada skrin.

Contoh 1:

• Input: n = 3
• Output: 3
• Penjelasan: Pada mulanya, kami mempunyai satu watak 'A'.
  • Dalam langkah 1, kami menggunakan operasi Salin Semua.
  • Dalam langkah 2, kami menggunakan operasi Tampal untuk mendapatkan 'AA'.
  • Dalam langkah 3, kami menggunakan operasi Tampal untuk mendapatkan 'AAA'.

Contoh 2:

• Input: n = 1
• Output: 0

Contoh 3:

• Input: n = 10
• Output: 7

Contoh 2:

• Input: n = 24
• Output: 9

Kekangan:

• 1 <= n <= 1000

Petunjuk:

1. Berapa banyak aksara yang mungkin terdapat dalam papan keratan pada langkah terakhir jika n = 3? n = 7? n = 10? n = 24?

Penyelesaian:

Kita perlu mencari bilangan operasi minimum untuk mendapatkan tepat n aksara 'A' pada skrin. Kami akan menggunakan pendekatan pengaturcaraan dinamik untuk mencapai matlamat ini.

1. Memahami Masalah:

   • Kita mulakan dengan satu 'A' pada skrin.
   • Kita boleh sama ada "Salin Semua" (yang menyalin kandungan skrin semasa) atau "Tampal" (yang menampal kandungan yang terakhir disalin).
   • Kami perlu menentukan operasi minimum yang diperlukan untuk mempunyai tepat n aksara 'A' pada skrin.

2. Pendekatan Pengaturcaraan Dinamik:

   • Gunakan dp tatasusunan pengaturcaraan dinamik (DP) dengan dp[i] mewakili bilangan operasi minimum yang diperlukan untuk mendapatkan aksara i tepat pada skrin.
   • Mulakan dp[1] = 0 kerana memerlukan 0 operasi untuk mempunyai satu 'A' pada skrin.
   • Untuk setiap bilangan aksara i dari 2 hingga n, kira operasi minimum dengan menyemak setiap pembahagi i. Jika i boleh dibahagi dengan d, maka:
     • Bilangan operasi yang diperlukan untuk mencapai i ialah jumlah operasi untuk mencapai d ditambah dengan operasi yang diperlukan untuk mendarab d untuk mendapatkan i.

3. Langkah untuk Menyelesaikan:

   • Memulakan tatasusunan DP dengan INF (atau nombor yang besar) untuk semua nilai kecuali dp[1].
   • Untuk setiap i daripada 2 hingga n, lelar melalui pembahagi yang mungkin bagi i dan kemas kini dp[i] berdasarkan operasi yang diperlukan untuk mencapai i dengan menyalin dan menampal.

Mari laksanakan penyelesaian ini dalam PHP: 650. Papan Kekunci 2 Kekunci

  
  
  Penjelasan:




Permulaan: dp dimulakan dengan nombor yang besar (PHP_INT_MAX) untuk mewakili keadaan pada mulanya tidak boleh dicapai.

Semakan Pembahagi: Bagi setiap nombor i, semak semua pembahagi d. Kemas kini dp[i] dengan mempertimbangkan operasi yang diperlukan untuk mencapai d dan kemudian mendarab untuk mendapatkan i.

Output: Hasilnya ialah nilai dp[n], yang memberikan operasi minimum yang diperlukan untuk mendapatkan tepat n aksara pada skrin.


Pendekatan ini memastikan kami mengira operasi minimum dengan cekap untuk kekangan yang diberikan.

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 . eys Papan Kekunci. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!