摘要：
=-1）返回dp[s][i]；2223dp[s][i]=0；24表示（intj=i；j=硬币[j]；j++）25dp[s][i]+=dfs（s-coin[j]，j）；2627返回dp[s][i]；28｝2930intmain（）｛31intn；32memset（dp，-1，sizeof（dp））；33 for（inti=0；i˂5；i++）dp[0][i]=1；34 while（scanf（“%d”，&n）！=EOF）｛3536printf（“%lld”，dfs（n，0））；37｝38 return0；39｝视图代码
题意：给出1,5,10,25,50五种硬币，再给出n,问有多少种不同的方案能够凑齐n
自己写的时候写出来方案数老是更少（用的一维的）
后来搜题解发现，要用二维的来写
http://blog.csdn.net/keshuai19940722/article/details/11025971
这一篇说的是会有面值的重复问题，还不是很理解
还有就是一个预处理的问题， 看了题解之后再自己写，很习惯的把处理dp数组写到while循环里面，一直tle
后来看到这篇题解
http://www.cnblogs.com/scau20110726/archive/2012/12/25/2832968.html
因为题目没有说会有多少组数据，如果把处理dp数组放在while循环里面的话，如果给出一个10w组的数据，那肯定就会超时(相当于每算一次，就要处理一次dp数组)
所以就把预处理放在外面就好啦
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 #define mod=1e9+7; 12 using namespace std; 13 14 typedef long long LL; 15 const int INF = 0x7fffffff; 16 const int maxn=8005; 17 LL dp[maxn][15]; 18 int coin[5]={1,5,10,25,50}; 19 20 LL dfs(int s,int i){ 21 if(dp[s][i]!=-1) return dp[s][i]; 22 23 dp[s][i]=0; 24 for(int j=i;j<5&&s>=coin[j];j++) 25 dp[s][i]+=dfs(s-coin[j],j); 26 27 return dp[s][i]; 28 } 29 30 int main(){ 31 int n; 32 memset(dp,-1,sizeof(dp)); 33 for(int i=0;i<5;i++) dp[0][i]=1; 34 while(scanf("%d",&n)!=EOF){ 35 36 printf("%lld ",dfs(n,0)); 37 } 38 return 0; 39 }