. clavier yeux

650. Clavier 2 touches

Difficulté :Moyen

Sujets : Mathématiques, programmation dynamique

Il n'y a qu'un seul caractère « A » sur l'écran d'un bloc-notes. Vous pouvez effectuer l'une des deux opérations sur ce bloc-notes pour chaque étape :

• Copier tout : Vous pouvez copier tous les caractères présents à l'écran (une copie partielle n'est pas autorisée).
• Coller : vous pouvez coller les caractères copiés la dernière fois.

Étant donné un entier n, renvoie le nombre minimum d'opérations pour obtenir le caractère 'A' exactement n fois à l'écran.

Exemple 1 :

• Entrée : n = 3
• Sortie : 3
• Explication : Initialement, nous avons un caractère 'A'.
  • À l'étape 1, nous utilisons l'opération Copier tout.
  • À l'étape 2, nous utilisons l'opération Coller pour obtenir « AA ».
  • À l'étape 3, nous utilisons l'opération Coller pour obtenir « AAA ».

Exemple 2 :

• Entrée : n = 1
• Sortie : 0

Exemple 3 :

• Entrée : n = 10
• Sortie :7

Exemple 2 :

• Entrée : n = 24
• Sortie :9

Contraintes :

• 1 <= n <= 1000

Indice :

1. Combien de caractères peuvent y avoir dans le presse-papiers à la dernière étape si n = 3 ? n = 7 ? n = 10 ? n=24 ?

Solution :

Nous devons trouver le nombre minimum d'opérations pour obtenir exactement n caractères 'A' à l'écran. Nous utiliserons une approche de programmation dynamique pour y parvenir.

1. Comprendre le problème :

   • Nous commençons par un « A » sur l'écran.
   • Nous pouvons soit "Copier tout" (qui copie le contenu actuel de l'écran) soit "Coller" (qui colle le dernier contenu copié).
   • Nous devons déterminer les opérations minimales requises pour avoir exactement n caractères 'A' à l'écran.

2. Approche de programmation dynamique :

   • Utilisez un tableau de programmation dynamique (DP) dp où dp[i] représente le nombre minimum d'opérations requises pour obtenir exactement i caractères à l'écran.
   • Initialisez dp[1] = 0 car il faut 0 opération pour avoir un 'A' à l'écran.
   • Pour chaque nombre de caractères i de 2 à n, calculez les opérations minimales en vérifiant chaque diviseur de i. Si i est divisible par d, alors :
     • Le nombre d'opérations nécessaires pour atteindre i est la somme des opérations pour atteindre d plus les opérations nécessaires pour multiplier d pour obtenir i.

3. Étapes à résoudre :

   • Initialisez un tableau DP avec INF (ou un grand nombre) pour toutes les valeurs sauf dp[1].
   • Pour chaque i de 2 à n, parcourez les diviseurs possibles de i et mettez à jour dp[i] en fonction des opérations nécessaires pour atteindre i en copiant et collant.

Implémentons cette solution en PHP : 650. Clavier 2 touches

  
  
  Explication:




Initialisation : dp est initialisé avec un grand nombre (PHP_INT_MAX) pour représenter un état initialement inaccessible.

Vérification des diviseurs : Pour chaque nombre i, vérifiez tous les diviseurs d. Mettez à jour dp[i] en considérant les opérations nécessaires pour atteindre d puis en multipliant pour obtenir i.

Sortie : Le résultat est la valeur de dp[n], qui donne les opérations minimales requises pour obtenir exactement n caractères à l'écran.


Cette approche garantit que nous calculons efficacement les opérations minimales pour les contraintes données.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!