首页 > 代码库 > UVA 674-Coin Change(DP)
UVA 674-Coin Change(DP)
题目链接:点击打开链接
题意 :有5种硬币的面值,分别为 1 ,5 ,10 ,25 ,50 。。 给出n 问用这些面值的硬币有多少种组成n的方式。(每种硬币无限,使用硬币数也无限)
两种做法,母函数比较长,以前也写过就不说了。。
第二种做法是DP 设 dp[i] 为组成i 的种类数,初始化dp[0]=1; (有图有真相 题目中原话 :Note that we count that there is one way of making change for zero cent) dp[i]=dp[i]+dp[i-v[j]] 枚举5种面值。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1<<12 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long using namespace std; int n,dp[7490]; int v[]={1,5,10,25,50}; void solve() { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<5;i++) for(int j=v[i];j<=n;j++) dp[j]+=dp[j-v[i]]; printf("%d\n",dp[n]); } int main() { while(~scanf("%d",&n)) solve(); return 0; }
UVA 674-Coin Change(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。