其实同种类型的题我不想重复发的，感觉没意思。这题又是硬币问题，和147、674原理一样。只是我在做这题时遇到了新的问题，也算是有新的收获，就发一下吧。我曾和zxpn讨论过是之前就算好所有结果，还是每输入一个就计算一个效率高。当时我认为肯定是输一个算一个好，因为把所有的都算出来，并不是每个都会用的，也算一种浪费；而DP时用记忆化搜索会保存每次调用的所有数，如果下次也要调用的话就不必再算了，明显更好。今天遇到这题DP不行了，原因是数很大时用递归形式的DP会导致栈溢出。下面是代码：
1 #include<stdio.h>
2 typedef long long int llg;
3 #define MAXN 30010
4 llg f[MAXN][6];
5 int coin[] = {1,5,10,25,50};
6 int main()
7 {
8 int a,i,j;
9 llg ans;
10 for(i = 0; i < MAXN; i++)
11 for(j = 0; j < 5; j++)
12 {
13 f[i][j] = 1;
14 for(int k = 1; k <= j && i >= coin[k]; k++)
15 f[i][j] += f[i-coin[k]][k];
16 }
17 while(scanf("%d",&a)==1)
18 {
19 ans = f[a][4];
20 if(ans != 1)
21 printf("There are %lld ways to produce %d cents change.\n",ans,a);
22 else
23 printf("There is only 1 way to produce %d cents change.\n",a);
24 }
25 return 0;
26 }