1 #include <stdio.h> 2 #include <stdlib.h> 3 int dp[20][20][20]; 4 int w(int a,int b,int c){ 5 if(a<=0||b<=0||c<=0){ 6 return 1; 7 } 8 if(a>20||b>20||c>20){ 9 return w(20,20,20); 10 } 11 if(dp[a][b][c]){//查找数组中是否有值，如果有，直接返回数组的值 12 return dp[a][b][c]; 13 } 14 if(a<b&&b<c){ 15 dp[a][b][c]= w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c); 16 } 17 else 18 dp[a][b][c]= w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1); 19 return dp[a][b][c]; 20 } 21 int main(){ 22 int a,b,c; 23 int num; 24 //第一种读入方法 25 freopen("input.txt","r",stdin); 26 //scanf("%d %d %d ",&a,&b,&c); 27 scanf("%d",&num); 28 for(int i=0;i<num;i++){ 29 scanf("%d",&a); 30 scanf("%d",&b); 31 scanf("%d",&c); 32 printf("w(%d, %d, %d) = %d ",a,b,c,w(a,b,c)); 33 } 34 //第二种读入方法 35 //while(~scanf("%d %d %d",&a, &b, &c)){ 36 //if(a==-1&&b==-1&&c==-1) 37 // break; 38 //printf("w(%d, %d, %d) = %d ",a,b,c,w(a,b,c)); 39 //} 40 //w(a,b,c); 41 system("pause"); 42 43 }
记忆化搜索：
求解的过程中按着自顶向下的顺序，但每求一个解的状态，就把他的解保存下来，以后再次遇到这个解的时候，就不必重新求解了。