我们都知道 递归是不断运行函数以得出结果的运算方式
它的优点在于 简单的几行公式就完全阐释了变换规律
当然 缺点也很明显：
如果要重复进行大数据的运算 会让计算时间极大幅度变长
因此 对递归的优化就尤为重要
首先 题目在这里
原超时代码如下
点击查看代码
#include <bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define foo(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
using namespace std;
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#define qr qr()
typedef long long ll;
const int Ratio=0;
const int N=2005;
const int maxx=0x7f7f7f7f;
int a,b,c,ans;
void read()
{
}
int DrRatio(int a,int b,int c)
{
if(a<=0||b<=0||c<=0)
return 1;
else if(a>20||b>20||c>20)
return DrRatio(20,20,20);
else if(a<b&&b<c)
return DrRatio(a,b,c-1)+DrRatio(a,b-1,c-1)-DrRatio(a,b-1,c);
else
return DrRatio(a-1,b,c)+DrRatio(a-1,b-1,c)+DrRatio(a-1,b,c-1)-DrRatio(a-1,b-1,c-1);
}
void op()
{
printf("w(%d, %d, %d) = %d\n",a,b,c,ans);
}
int main()
{
read();
while(scanf("%d%d%d",&a,&b,&c))
{
if(a==-1&&b==-1&&c==-1)
break;
ans=DrRatio(a,b,c);
op();
}
return Ratio;
}
原代码的计算方式没有问题 超时的原因 题目中也给出了 当求w（15,15,15）时就会进行几小时的冗长计算
优化后更改如下：
int zl[N][N][N];
int DrRatio(int a,int b,int c)
{
if(a<=0||b<=0||c<=0)
return 1;
else if(a>20||b>20||c>20)
return DrRatio(20,20,20);
else if(zl[a][b][c])
return zl[a][b][c];
else if(a<b&&b<c)
return zl[a][b][c]=DrRatio(a,b,c-1)+DrRatio(a,b-1,c-1)-DrRatio(a,b-1,c);
else
return zl[a][b][c]=DrRatio(a-1,b,c)+DrRatio(a-1,b-1,c)+DrRatio(a-1,b,c-1)-DrRatio(a-1,b-1,c-1);
}
可以看到 添加了一个三维数组 用来存储已经处理过的数据
由题目可以明显得知 在进行数据大一点的运算时 会重复多次计算
因此 增加一个记录处理好的值的数组 会大大减少运算量 使得每组数据只被计算一次
这种类似的构造类函数还有阿克曼函数
