Количество комбинаций с пластиковыми кубиками LEGO C++

У вас есть несколько пластиковых кубиков LEGO, все кубики 1x1x1. Также у вас есть одна плитка, 1xN (N

Вот пример.:

Если плитка имеет размер 1x7, существует 17 различных комбинаций.

вход :7 output :17

_{(source:mendo.mk)}

Также, если у вас нет кирпичей, это считается за 1 комбинацию.

Я работал над этой проблемой и нашел способ вычислить возможные комбинации, если максимальная длина плитки составляет 14 (3 последовательности ). Я нашел это, используя циклы for.

Моя самая большая проблема — это огромное количество циклов for, которые мне нужно запустить. Например, для 1 последовательности я использую 1 для петель, для 2 последовательностей 2 петли + 1 для 1 последовательности... поэтому, если я использую все 80 кирпичей, я могу создать 20 последовательностей, и мне придется использовать более 210 для петель, что составляет огромное количество. Так что будет хорошо, если я смогу вложить их в один. Я попробовал это, и это становится грязным, и это не дает правильных ответов.

Новый код:

#include 
using namespace std;
int main()
{
    long long int places, combinations = 1;
    cin >> places;
    long long int f[80], g[80];
    f[0] = 0;
    f[1] = 0;
    f[2] = 0;
    g[0] = 1;
    g[1] = 1;
    g[2] = 1;
    for(int i = 3; i<=places; i++)
    {
        f[i] = f[i-1] + g[i-3];
        g[i] = f[i-1] + g[i-1];
    }
    combinations = f[places] + g[places];
    cout << combinations;
    return 0;
}