Count sequences

Question 1

Dans quel type de problème est-il utile de compter des séquences (et pas juste des éléments) ?

Answer 1

Quand il faut placer des éléments sous contrainte (ex : interdiction d’être côte à côte, besoin d’espacement, intervalles minimums, etc.).

Question 2

Quelle est l’idée centrale du “comptage de séquences” ?

Answer 2

Parcourir une structure (liste, chaîne…) et compter les suites continues d’états favorables (ex: zéros, espaces vides) pour calculer globalement combien d’actions/placements sont possibles.

Question 3

Quelle formule générale utilise-t-on pour estimer ce qu’on peut faire avec une séquence de longueur k ?

Answer 3

Utiliser une formule adaptée du type :

(fonction de k selon la contrainte du problème)

Par exemple : (k-1)//2 si on doit séparer par au moins 1 case.

Question 4

Pourquoi initialise-t-on parfois le compteur avec une valeur spéciale (ex: 1 au lieu de 0) ?

Answer 4

Pour intégrer implicitement les bordures (début/fin) et éviter des traitements spéciaux.

Question 5

Quel est l’avantage de ce pattern en complexité et propreté de code ?

Answer 5

✅ Complexité en O(n)
✅ Évite les conditions lourdes case par case
✅ Code lisible et modulaire
✅ S’adapte à plein de variations du problème.

Question 6

Résumé express du pattern à retenir ?

Answer 6

“Repérer les séquences favorables en un seul passage, calculer ce qu’on peut en tirer, et traiter le bord intelligemment.”