![. eys Keyboard](https://img.php.cn/upload/article/000/000/000/172410864672437.jpg)
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, renvoiele 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 :
Exemple 3 :
Exemple 2 :
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 audépôtsur 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!