С++ Без трёх единиц

Динамическим программированием за 1 проход:

int n;
long t[40][4] = {0};
t[0][0] = 1;
t[0][1] = 1;
cin >> n;
for (int i = 1; i < n; ++i) {
t[i][0] = t[i - 1][0] + t[i - 1][2];
t[i][1] = t[i - 1][0] + t[i - 1][2];
t[i][2] = t[i - 1][1] + t[i - 1][3];
t[i][3] = t[i - 1][1];
}
cout << t[n - 1][0] + t[n - 1][1] + t[n - 1][2] + t[n - 1][3];

Просто рассматриваем два очередных числа последовательности как биты двоичного числа диапазона 0..3. При добавлении нового числа дописываем его справа и отбрасываем бит слева. И считаем кол-во способов, которым можем получить каждую комбинацию двух битов.

00 + 0 => 00
10 + 0 => 00
00 + 1 => 01
10 + 1 => 01
01 + 0 => 10
11 + 0 => 10
01 + 1 => 11
11 + 1 => запрещено, три единицы подряд

Т. к. t[i][0] и t[i][1] всегда равны, можно упростить:

int n;
long t[40][3] = {0};
t[0][0] = 1;
cin >> n;
for (int i = 1; i < n; ++i) {
t[i][0] = t[i - 1][0] + t[i - 1][1];
t[i][1] = t[i - 1][0] + t[i - 1][2];
t[i][2] = t[i - 1][0];
}
cout << t[n - 1][0] * 2 + t[n - 1][1] + t[n - 1][2];

Стоит завести строку из "0" и "1". Каждый раз эту строку изменяешь на новое состояние (новую последовательность).
В цикле пробегаешь строку с шагом в три. И проверяешь для трех элементов, что все они равны "1". Если такое встретилось, то continue для основного цикла и переход в новое состояние, если не встретилось, то +1 счетчик.

Если ты решаешь курс Сириус. Информатика. Регионы. Ноябрь 2021. 7–8 класс, то присоединяйся к беседе по ссылке: tinyurl.com/2wsb3994