2466. Compter les façons de construire de bonnes cordes

2466. Compter les façons de construire de bonnes cordes

Difficulté : moyenne

Sujets :Programmation dynamique

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

• Ajouter le personnage'0'zérofois.
• Ajouter le personnage'1'unfois.

Cela peut être effectué plusieurs fois.

Une bonne chaîne est une chaîne construite par le processus ci-dessus ayant une longueur comprise entrefaibleethaut(compris).

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

Exemple 1 :

• Entrée : faible = 3, élevé = 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...
    [Courte citation de 8% de l'article original]