. clavier yeux

WBOY
WBOYoriginal
2024-08-20 07:04:051120parcourir

. eys Keyboard

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!

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