10/07/10 10:10:43
>>589
該当する関数をこれに置き換えると早くなる
int coin_func_r(int result[], int c[], int m, int n){
int i, num;
if(m<0 || result[m]==0) return -1;
if(result[m]>0) return result[m];
for(i=0;c[i]>0;i++){
num=coin_func_r(result, c, m-c[i], n+1);
if(num>0 && (result[m]<0 || result[m]>num+1)) result[m]=num+1;
}
if(result[m]<0) result[m]=0;
return result[m];
}
int coin_func(int c[], int amount){
int i, lcm_all=1, rest, c_max=1, *result, ret;
for(i=0;c[i]>0;i++){
lcm_all=lcm(lcm_all, c[i]);
if(c_max<c[i]) c_max=c[i];
}
result=calloc(lcm_all, sizeof(int));
for(i=0;i<lcm_all;i++) result[i]=-1;
for(i=0;c[i]>0;i++) result[c[i]]=1;
rest=amount%lcm_all;
coin_func_r(result, c, rest, 0);
ret=result[rest]+(amount-rest)/c_max;
free(result);
return ret;
}