动态规划 多重幂计数

时间限制: 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取得足够大，暂且不说费时的问题，直接就会因为递归次数太多，函数堆栈溢出而 程序奔溃。我们可以将已经求得的 子问题的结果保存下来，这样对子问题只会求解一次，这便是记忆化搜索。下面在上述逻辑的基础上加上记忆化搜索：

#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/