. 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.

Diberi integer n, kembalikanbilangan minimum operasi untuk mendapatkan aksara 'A' tepat n kali pada skrin.

Contoh 1:

• Input:n = 3
• Output:3
• Penjelasan:Pada mulanya, kita 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).
   • Kita 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.
   • Inisialisasikan dp[1] = 0 kerana diperlukan 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 Penyelesaian:

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

Mari kita 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 dapat 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.
Hubungi Pautan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna buat 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!