动态规划 多重幂计数

原创
2021/08/23 00:03
阅读数 5


时间限制: 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/




本文分享自微信公众号 - WebHub(myWebHub)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部