coin change

2020-02-09 16:01:04来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

coin change

首先考虑没有限制的情况

当硬币被限制数量,需要加入对硬币情况的考虑

所以设dp[][]

记录凑齐x的种类

代码如下

#include <iostream>
using namespace std;
int main(){
int dp[251][101]={0},ans[251]={0};
int type[5]={1,5,10,25,50},x,i,j,k;
dp[0][0]=1;
for(i=0;i<5;i++)
for(j=1;j<101;j++)
for(k=type[i];k<251;k++)
dp[k][j]+=dp[k-type[i]][j-1];
for(i=0;i<251;i++)
for(j=0;j<101;j++)
ans[i]+=dp[i][j];

while(cin >> x){
cout << ans[x] << endl;
}

return 0;
}

咳咳,没了


原文链接:https://www.cnblogs.com/sos3210/p/12288982.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Longest Ordered Subsequence

下一篇:Codeforces Round #617 (Div. 3)