Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <unordered_map>
#include <vector>
//------------------------------------------------------------------------
long long bst_count_classic(int n)
{
if (n <= 1) return 1;
std::vector<long long> memo(n+1, 0);
memo[0] = memo[1] = 1;
for (int k = 2; k <= n; ++k)
{
for (int i = 0; i < k; ++i)
{
memo[k] += memo[i] * memo[k-i-1];
}
}
return memo.back();
}
//------------------------------------------------------------------------
template<typename Recur>
long long bst_count(Recur recur, int n)
{
if (n <= 1) return 1;
long long sub_counts = 0;
for (int i = 0; i < n; ++i)
sub_counts += recur(i) * recur(n - i - 1);
return sub_counts;
}
//------------------------------------------------------------------------
long long best_count_fix_point(int n)
{
return bst_count([](int k) { return best_count_fix_point(k); }, n);
}
long long bst_count_memo(int n)
{
std::vector<long long> memo(n+1);
for (int i = 0; i <= n; ++i)
memo[i] = bst_count([&](int k) { return memo[k]; }, i);
return memo.back();
}
//------------------------------------------------------------------------
static long long lazy_impl(std::vector<long long>& memo, int n)
{
if (memo[n]) return memo[n];
auto recur = [&](int k) { return lazy_impl(memo, k); };
return memo[n] = bst_count(recur, n);
}
long long bst_count_lazy(int n)
{
std::vector<long long> memo(n+1);
return lazy_impl(memo, n);
}
//------------------------------------------------------------------------
static long long lazy_map(std::unordered_map<int, long long>& memo, int n)
{
auto& computed = memo[n];
if (computed) return computed;
auto recur = [&](int k) { return lazy_map(memo, k); };
return computed = bst_count(recur, n);
}
long long bst_count_map(int n)
{
std::unordered_map<int, long long> memo;
return lazy_map(memo, n);
}
//------------------------------------------------------------------------
template<typename TestFct>
static void bench_it(TestFct testFct)
{
int runs = 100;
int N = 1000;
for (int i = 0; i < runs; ++i)
{
testFct(N);
}
}
void example()
{
bench_it(bst_count_memo);
bench_it(bst_count_lazy);
bench_it(bst_count_map);
bench_it(bst_count_classic);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment