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 :
Indice :
- 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.
-
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.
-
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.
-
É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 :
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!
Déclaration:Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn