Comptez les façons de créer de bonnes cordes

2466. Comptez les façons de créer de bonnes cordes

Difficulté :Moyen

Sujets : Programmation dynamique

Étant donné les entiers zéro, un, faible et élevé, nous pouvons construire une chaîne en commençant par une chaîne vide, puis à chaque étape effectuer l'une des opérations suivantes :

• Ajoutez le caractère « 0 » zéro fois.
• Ajoutez le caractère « 1 » une fois.

Cela peut être effectué autant de fois que vous le souhaitez.

Une bonne chaîne est une chaîne construite par le processus ci-dessus ayant une longueur entre basse et haute (inclusive).

Renvoyer le nombre de différentes bonnes chaînes qui peuvent être construites satisfaisant ces propriétés. Puisque la réponse peut être grande, renvoyez-la modulo 10⁹ 7.

Exemple 1 :

• Entrée : bas = 3, haut = 3, zéro = 1, un = 1
• Sortie : 8
• Explication :
  • Une bonne chaîne valide possible est "011".
  • Il peut être construit comme suit : "" -> "0" -> "01" -> "011".
  • Toutes les chaînes binaires de "000" à "111" sont de bonnes chaînes dans cet exemple.

Exemple 2 :

• Entrée : bas = 2, haut = 3, zéro = 1, un = 2
• Sortie : 5
• Explication : Les bonnes chaînes sont "00", "11", "000", "110" et "011".

Contraintes :

• 1 <= faible <= élevé <= 10⁵
• 1 <= zéro, un <= faible

Indice :

1. Calculez le nombre de bonnes chaînes d'une longueur inférieure ou égale à un x constant.
2. Appliquez une programmation dynamique en utilisant la taille du groupe de zéros et de uns consécutifs.

Solution :

Nous devons nous concentrer sur la construction de chaînes de différentes longueurs et compter le nombre de chaînes valides qui remplissent les conditions données. Décomposons l'approche :

Répartition du problème

1. Définition de l'État :
   Laissez dp[i] représenter le nombre de chaînes valides de longueur i qui peuvent être construites en utilisant les valeurs zéro et un fournies.

2. Relation de récidive :

   • De n'importe quelle longueur i, nous pouvons ajouter soit :
     • zéro 0 consécutifs, donc la chaîne précédente serait de longueur i-zero, et nous ajouterions des façons dp[i-zero].
     • un 1 consécutif, donc la chaîne précédente serait de longueur i-one, et nous ajouterions des façons dp[i-one].

La relation de récurrence devient :
dp[i] = dp[i - zéro] dpi - un

1. Cas de base :

   • Il existe exactement une façon de construire une chaîne vide : dp[0] = 1.

2. Calcul final :

   • Le nombre total de chaînes valides de longueur comprise entre bas et haut est la somme de dp[i] pour tous les i de bas en haut.

Étapes de la solution

1. Initialisez un tableau dp de taille élevée 1 où chaque index i représente le nombre de chaînes valides de longueur i.
2. Parcourez chaque longueur possible i de 1 à haut, en mettant à jour dp[i] en fonction de la relation de récurrence.
3. Calculez la somme de dp[i] de bas en haut pour obtenir le résultat final.

Implémentons cette solution en PHP : 2466. Comptez les façons de créer de bonnes cordes

  
  
  Explication:




Initialisation : Nous commençons par définir le cas de base dp[0] = 1, ce qui signifie qu'il existe une façon de former une chaîne de longueur 0 (la chaîne vide).

Mise à jour de la programmation dynamique : Pour chaque longueur de chaîne possible i de 1 à haute, nous vérifions si nous pouvons ajouter une chaîne de longueur zéro ou un à une chaîne plus petite. Nous mettons à jour dp[i] en conséquence en ajoutant le nombre de façons de former une chaîne de longueur i-zero et i-one, en nous assurant que le résultat est pris modulo 109 7.

Calcul du résultat final : Nous résumons toutes les valeurs de dp[i] pour i dans la plage [low, high] pour obtenir le nombre final de chaînes valides.



  
  
  Complexité temporelle :



Le remplissage du tableau dp prend O (haut).
La sommation des résultats valides entre bas et haut prend O (haut - bas 1).


Ainsi, la complexité temporelle globale est ** O(high) **, ce qui est suffisamment efficace pour les limites d'entrée.


  
  
  Complexité spatiale :



Nous utilisons un tableau dp de taille haute 1, donc la complexité spatiale est O(haute).


Cette solution résout efficacement le problème dans les limites des contraintes.

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!