多重幂计数问题
时间： 1ms 内存：64M
描述：
设给定n个变量x1 , x2 ,…, xn 。将这些变量依序作底和各层幂，可得n重幂如下:
这里将上述n重幂看作是不确定的，当在其中加入适当的括号后，才能成为一个确定的n重幂。不同的加括号方式导致不同的n重幂。例如，当n=4时，全部4重幂有5个。对n个变量计算出有多少个不同的n重幂。
输入：
输入数据只有一行，提供一个数n（n≤50）。
输出：
输出数据只有一行，表示找到的序关系数。
示例输入：
4示例输出：
5提示：
参考答案（内存最优[1484]）：
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll f[51];
ll dfs(int n)
{
if(f[n])return f[n];
ll t=0;
for(int i=1;i<n;++i)
{
t+=dfs(n-i)*dfs(i);
}
return f[n]=t;
}
int main()
{
f[0]=f[1]=f[2]=1;
int n;
while(cin>>n)
cout<<dfs(n)<<endl;
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll f[51];
ll dfs(int n)
{
if(f[n])return f[n];
ll t=0;
for(int i=1;i<n;++i)
{
t+=dfs(n-i)*dfs(i);
}
return f[n]=t;
}
int main()
{
f[0]=f[1]=f[2]=1;
int n;
while(cin>>n)
cout<<dfs(n)<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。