POJ 1579 Function Run Fun 记忆化搜索
来源：http://poj.org/problem?id=1579
题意：题目就是给了你一个递归方程，然后让计算值。
思路：由于递归太慢，而且计算了很多重复的值，所以可以用记忆化搜索，标记计算过的值即可。如果已经计算过了，直接返回就可以了。
代码：
#include <iostream>#include <cstdio>#include <string.h>using namespace std;int ans[22][22][22];int fun(int x,int y,int z){if(x <= 0 || y <= 0 || z <= 0){return 1;}if(ans[x][y][z] != -1)return ans[x][y][z];else if(x < y && y < z)return fun(x,y,z-1) + fun(x,y-1,z-1) - fun(x,y-1,z);else return fun(x-1,y,z) + fun(x-1,y-1,z) + fun(x-1,y,z-1) - fun(x-1,y-1,z-1);}void init(){memset(ans,-1,sizeof(ans));for(int i = 0; i <= 20; ++i){for(int j = 0;j <= 20; ++j){for(int k = 0; k <= 20; ++k){ ans[i][j][k] = fun(i,j,k);}}}}int main(){//freopen("1.txt","w",stdout);int a,b,c;init();while(scanf("%d%d%d",&a,&b,&c)){ if(a + b + c == -3) break; if(a < 0 || b < 0 || c < 0) printf("w(%d, %d, %d) = %d\n",a,b,c,1); else{ int aa = a,bb = b,cc = c; if(a > 20 || b > 20 || c > 20){ aa = 20;bb = 20;cc= 20; } printf("w(%d, %d, %d) = %d\n",a,b,c,ans[aa][bb][cc]); }}return 0;}