Numero di possibile partizionamento della sequenza

Question

Data una sequenza di 1 e 0 elementi, qual è il numero di possibili partizionamento della sequenza nelle sotto-sequenze (non necessariamente elementi consecutivi e sono consentiti un numero qualsiasi di sotto-sequenze) in modo che qualsiasi sottosequenza inizi e finisca con a 1 e può contenere un numero arbitrario di 0s?

Ad esempio: data la sequenza 1 0 1 1 0 1 Esistono solo 3 modi per partizionare la sequenza:

1.
1 0 1
      1 0 1

2.
1 0     0 1
    1 1

3.
1 0   1
    1   0 1

Sono abbastanza sicuro che la soluzione implica una programmazione dinamica, poiché la soluzione richiede un tempo di esecuzione rapido (<1 secondo).