时间限制: 1 Sec 内存限制: 128 MB
多重幂计数就是指数塔的组合最优解问题,设给定的n个变量X1,X2,...,Xn。将这些变量依序作底和各层幂,可得n重幂如下:
这里将上述 n 重幂看作是不确定的,当在其中加入适当的括号后,才能成为一个确定的
n 重幂。不同的加括号方式导致不同的 n 重幂。例如,当 n=4 时,全部 4 重幂有 5 个。
«编程任务:
对 n 个变量计算出有多少个不同的 n 重幂。
只有一行,提供一个数 n 。
将找到的序关系数输出
4
5
动态规划是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。动态规划则通过填写表把所有已经解决的子问题答案记录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。
基本算法-动态规划
既然该题属于动态规划类型,自然想到利用递归函数解决问题。首先进行数学建模,想办法将具象世界中的问题抽象成几何图形,然后就可以用图论中的算法解决,我们把图中的指数塔横过来,变成:
X1^X2^X3^...^Xn
这样就形成了共线的线段,因为相邻的2个X可以用括号融并成1个新X,新X又可以和相邻的X融并,所有的X可以作为二叉树的叶子,叶子们的顺序不变,非叶子结点都有2个子树,所以问题变成了含有n个叶子的二叉树,总共有多少种这样的树?
画图工具:processon.com
要求解F(n),从根部开始分析,假设左边m个X,右边有n-m个X,那么左子树有F(m)种情况,右子树有F(n-m)种情况,则对于每个m,共F(m)*F(n-m)种,而m又有n-1种情况,所以把这n-1种情况全部相加才能得出结果。
递归算法依赖复杂度最小的几项的结果,通过简单的穷举,我们得到n在5以内的F(n):
n | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
F(n) | 0 | 1 | 1 | 2 | 5 |
我们用递归可以很简单的实现以上代码,但是有个严重的问题就是, 直接采用自顶向下的递归算法会导致 要不止一次的解决公共子问题,因此效率是相当低下。如果n取得足够大,暂且不说费时的问题,直接就会因为递归次数太多,函数堆栈溢出而 程序奔溃。我们可以将已经求得的 子问题的结果保存下来,这样对子问题只会求解一次,这便是记忆化搜索。下面在上述逻辑的基础上加上记忆化搜索:
#include<iostream>
#include<algorithm>
using namespace std;
long long f[1001] = {0, 1, 1, 2};
inline long long search(int T)
{
if(f[T])return f[T];
for(int i = 1; i < T; i++)
{
f[T] += search(T - i) * search(i);
}
return f[T];
}
int main()
{
int n;
while(cin >> n)cout << search(n) << endl;
return 0;
}
/**************************************************************
Problem: 22497
User: jim
Language: C++
Result: 正确
Time:3 ms
Memory:2184 kb
****************************************************************/
题目来源:TK题库:http://tk.hustoj.com/