题意：在一个国家仅有1分，2分，5分硬币，将n（n>=5）分钱兑换成硬币有很多种兑法。求有多少种兑换方式。
第一种解法：
通过枚举3的种类数，当你已知3的个数就可以求出2的种类，以此类推,3的个数确定，2的个数也可以确定，剩下的就是1，假设3的个数为x（0<=x<=n/3）,那么2的个数就是（n-3*i）/2,再然后1的个数就确定了。
#include<bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n){ int i,j,ans=0; for(i=0;i<=n/3;i++){ int temp=(n-3*i); ans+=temp/2+1; } cout<<ans<<endl; } }
第二种解法：
类似完全背包dp， 比较经典的dp问题，外层循环是硬币的价值，可以一个一个枚举，如果i=1，那么则一直放1，求出方案数，其他同理。
#include<bits/stdc++.h> using namespace std; const int maxn=32768+10000; int dp[maxn]; int main() { int n,i,j; while(~scanf("%d",&n)){ memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=3;i++){ for(j=i;j<=n;j++){ dp[j]+=dp[j-i]; } } cout<<dp[n]<<endl; } }
