Question

СРОЧНО!!! Без трёх единиц
Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.

Входные данные:
Дано натуральное число N, не превосходящее 40.

Выходные данные:
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231−1.

Answer 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];

}