Без трёх единиц Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.
Входные данные: Дано натуральное число N, не превосходящее 40.
Выходные данные: Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231−1.
#include <iostream>
using namespace std;
long long int dp[40];
int main() {
dp[0]=2;
dp[1]=4;
dp[2]=7;
for (int i=3; i<40; i++)
dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
int n;
cin>>n;
cout<<dp[n-1];
}