#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;
}