#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

using ull = unsigned long long;

struct pair_hash
{
    template <typename T1, typename T2>
    std::size_t operator ()(const std::pair<T1, T2>& pair) const
    {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

using TMem = std::unordered_map<std::pair<int,int>, ull, pair_hash>;

// Количество разложений для N блоков равно сумме количеств
// разложений ,где максимальная длина нижнего уровня уровня
// равна N-1,N-2,....
struct task135_recurse
{
    ull operator ()(int N)
    {
        return solve(N, N);
    }

private:
    ull solve(int N, int maxN)
    {
        ull result = 0;

        if (N < 0) {
            return 0;
        }

        if (N == 0) {
            return 1;
        }

        for (int i = maxN; i > 0; --i) {
            result += solve(N - i, i - 1);
        }

        return result;
    }
};

// Оптимизация для предыдущего алгоритма. Запоминаем уже вычисленные
// значения (мемоизация) чтобы не вычислять одно и тоже. По моим
// замерам закэшировать удается до 90% значений
struct task135_recurse_memo
{
    ull operator ()(int N)
    {
        TMem mem;
        return solve(N, N, mem);
    }

    std::pair<ull, ull> GetStats()
    {
        return make_pair(Calls, Hits);
    }

private:
    ull solve(int N, int maxN, TMem& mem)
    {
        auto it = mem.find(std::make_pair(N,maxN));

        ++Calls;
        if (it != mem.end()) {
            ++Hits;
            return it->second;
        }

        ull result = 0;

        if (N == 0) {
            result = 1;
        }


        if (N > 0) {
            for (int i = maxN; i > 0; --i) {
                result += solve(N - i, i - 1, mem);
            }
        }

        mem[std::make_pair(N,maxN)] = result;

        return result;
    }
private:
    ull Calls = 0;
    ull Hits = 0;
};

// Здесь мы считаем туже формулу. Но на этот раз
// идем нет от конца к началу , а от начала к концу
// За счет этого избавляемся от рекурсии, но возможно
// проигрываем по памяти и делаем возможно лишнюю работу
// поскольку не знаем какие значения понадобятся потом
struct task135_dynamic_array
{
    ull operator ()(int N)
    {
        return solve(N);
    }

private:
    ull get(vector<vector<ull>>& a, int i, int j)
    {
        if (i < 0 || j < 0) {
            return 0;
        }
        return a[i][j];
    }

    ull solve(int N)
    {
        vector<vector<ull>> a(N+1, vector<ull>(N+1));

        for (int i = 0; i < N; ++i) {
            a[0][i] = 1;
        }
        for (int i = 1; i < N+1; ++i) {
            for (int j = 1; j < N+1; ++j) {
                for (int k = j; k > 0; --k) {
                    a[i][j] += get(a, i - k, k - 1);
                }
            }
        }
        return a[N][N];
    }
};


// Определим решение немного иначе.
// Количество разложений для N блоков равно сумме количеств
// разложений двух типов
// 1. на нижнем уровне лежит блок длины N
// 2. на нижнем уровне лежит блок длины меньше N

struct task135_recurse1
{
    ull operator ()(int N)
    {
        return solve(N, N);
    }

private:
    ull solve(int N, int maxN)
    {
        ull result = 0;

        if (N < 0 || (maxN == 0 && N != 0)) {
            return 0;
        }

        if (N == 0) {
            return 1;
        }

        result += solve(N - maxN, maxN - 1) + solve(N, maxN - 1);

        return result;
    }
};

// Мемоизация предыдущего алгоритма. Опять не вычисляем уже
// вычисленные значения. Для мойих тестов экономилось до 20%
// вычислений (См. GetStats метод).
struct task135_recurse_memo1
{
    ull operator ()(int N)
    {
        TMem mem;
        return solve(N, N, mem);
    }

    std::pair<ull, ull> GetStats()
    {
        return make_pair(Calls, Hits);
    }

private:
    ull solve(int N, int maxN, TMem& mem)
    {
        auto it = mem.find(std::make_pair(N,maxN));

        ++Calls;
        if (it != mem.end()) {
            ++Hits;
            return it->second;
        }

        ull result = 0;

        if (N == 0 && maxN >= 0) {
            return 1;
        }

        if (N > 0 && maxN > 0) {
            result += solve(N - maxN, maxN - 1, mem) + solve(N, maxN - 1, mem);
        }

        mem[std::make_pair(N,maxN)] = result;

        return result;
    }
private:
    ull Calls = 0;
    ull Hits = 0;
};

// Опять нерекурсивная динамика.
// Одем от тачала к концу (от 1 к N)
// За счет этого избавляемся от рекурсии,
// но получаем избыточность по памяти и лишние вычисления
// для ячеек которые возможно не будут нужны
struct task135_dynamic_array1
{
    ull operator ()(int N)
    {
        return solve(N);
    }

private:
    ull get(vector<vector<ull>>& a, int i, int j)
    {
        if (i < 0 || j < 0) {
            return 0;
        }
        return a[i][j];
    }

    ull solve(int N)
    {
        vector<vector<ull>> a(N+1, vector<ull>(N+1));

        for (int i = 0; i < N; ++i) {
            a[0][i] = 1;
        }
        for (int i = 1; i < N+1; ++i) {
            for (int j = 1; j < N+1; ++j) {
                a[i][j] = get(a, i-j,j-1) + get(a, i,j-1);
            }
        }
        return a[N][N];
    }
};


int main() {

    // Прогоняем тесты для всех 6 реализаций задачи
    // вычисляем значение для всех значений от 1 до 100
    // печатаем и убеждаемся что все они совпадают

    vector<ull> r1;
    for (int i = 1; i < 101; ++i) {
        r1.push_back(task135_recurse()(i));
    }

    vector<ull> r2;
    for (int i = 1; i < 101; ++i) {
        auto a = task135_recurse_memo();
        r2.push_back(a(i));
        //cout << a.GetStats().first << " " << a.GetStats().second << endl;
    }

    vector<ull> r3;
    for (int i = 1; i < 101; ++i) {
        r3.push_back(task135_recurse1()(i));
    }

    vector<ull> r4;
    for (int i = 1; i < 101; ++i) {
        auto a = task135_recurse_memo1();
        r4.push_back(a(i));
        //cout << a.GetStats().first << " " << a.GetStats().second << endl;
    }

    vector<ull> r5;
    for (int i = 1; i < 101; ++i) {
        r5.push_back(task135_dynamic_array()(i));
    }

    vector<ull> r6;
    for (int i = 1; i < 101; ++i) {
        r6.push_back(task135_dynamic_array1()(i));
    }

    for (int i = 0; i < 100; ++i) {
        cout << (i+1) << "-> " << r1[i] << " " << r2[i] << " " << r3[i] << " " << r4[i] << " " << r5[i] << " " << r6[i] << endl;
    }

    return 0;

}