Nombre de partitions de séquence possibles

Question

Compte tenu d'une séquence d'éléments 1 et 0, quel est le nombre de partitions possibles de la séquence dans les sous-séquences (pas nécessairement des éléments consécutifs, et n'importe quel nombre de sous-séquences sont autorisés) de sorte que toute sous-séquence commence et se termine par un 1, et peut contenir un nombre arbitraire de 0s?

Par exemple: étant donné la séquence 1 0 1 1 0 1 Il n'y a que 3 façons de partitionner la séquence:

1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

Je suis à peu près sûr que la solution implique une programmation dynamique, car la solution nécessite un temps d'exécution rapide (<1 seconde).