钱币兑换问题（dp背包）
发布时间
阅读量：
阅读量
钱币兑换问题
在一个国家里只有面值为1分、2分和3分的硬币。兑换金额为N的货币成硬币有很多种组合方式。请编写程序以计算出相应的兑换方法数量。
思路：逐步递增3分硬币的数量，在余下金额的基础上可以选择插入一个2分硬币或两个1分硬币，在此基础之上再添加一枚1分，则所有情况均转化为全1分的情形
ac代码：
#include<iostream>
using namespace std;
long long int a[1000000];
int main(){
long long int n;
while(cin>>n){
long long int ans=0;
for(int i=0;i<=n/3;i++){
int temp=n-i*3;
ans+=temp/2+1;
}
cout<<ans<<endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~