млин, это же легко...
короче, заведем двухмерный массив a[i, j], где i - длина последовательности, j - на что оканчивается (0 или 1)

a[1, 1] = 1
a[1, 0] = 1

потом, к нолику мы можем дописать или 0 или 1, т. е. a[i, 0] = a[i - 1, 0] + a[i - 1, 1]
к единице только нолик, т.е. a[i, 1] = a[i - 1, 0]
результат в a[n, 0] + a[n, 1]

как-то так