文章
11
粉丝
216
获赞
4
访问
102.8k
#include<iostream>
#include<cstring>
using namespace std;
long long num[25]; //用于记忆化搜索,不然会超时
long long cntBitree(int n)
{
if (num[n] > 0) return num[n]; //已经计算,直接返回结果
long long cnt = 0;
for (int i = 1; i < n; i++)
{
cnt += cntBitree(i) * cntBitree(n - i - 1); //模拟左右子树的结点变化,减1是因为根结点占了一个结点数
}
//加上线性的两种情况
cnt += cntBitree(n - 1) * 2;
num[n] = cnt;
return cnt;
}
int main()
{
int n;
memset(num, 0, sizeof(num));
num[1] = 1; //边界情况
num[0] = 0;
while (cin >> n)
{
cout << cntBitree(n) << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发