本文主要是介绍钱币兑换问题（dp+数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：在一个国家仅有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;}
}
这篇关于钱币兑换问题（dp+数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
