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

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 avec un « A » à 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 pour 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 en 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 du diviseur : 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