UVa 674 Coin Change

题目描述给定555种硬币505050美分、252525美分、101010美分、555美分和111美分。对于任意金额单位美分求用这些硬币组成该金额的不同方式数不考虑顺序。金额最大为748974897489美分。输入格式多行输入每行一个整数表示金额单位美分。输出格式对于每个金额输出一行整数表示不同的组成方式数。样例输入11 26输出4 13题目分析本题是完全背包问题硬币无限使用的组合计数且硬币面额固定。使用动态规划dp[i][j]表示使用前i种硬币组成金额j的方式数。状态转移为不使用第i种硬币dp[i-1][j]使用第i种硬币dp[i][j - coins[i]]至少使用一枚最终dp[5][j]即为答案。解题思路定义硬币面额数组coins[1..5] {1, 5, 10, 25, 50}。初始化dp[0][0] 1其余为 0。对每种硬币i从 1 到 5对金额j从 0 到MAXdp[i][j] dp[i-1][j]不用该种硬币若j coins[i]则dp[i][j] dp[i][j - coins[i]]用该种硬币查询时直接输出dp[5][cents]。由于金额最大 7489使用long long存储结果数量可能较大。复杂度分析预计算O(5×7490)O(5 \times 7490)O(5×7490)约3.7×1043.7 \times 10^43.7×104极快。查询O(1)O(1)O(1)。代码实现// Coin Change// UVa ID: 674// Verdict: Accepted// Submission Date: 2016-08-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcoins[6]{0,1,5,10,25,50};longlongintways[6][7500];memset(ways,0,sizeof(ways));ways[0][0]1;for(inti1;i5;i)for(intj0;j7489;j){ways[i][j]ways[i-1][j];if(j-coins[i]0)ways[i][j]ways[i][j-coins[i]];}intcents;while(cincents)coutways[5][cents]\n;return0;}总结本题是完全背包计数问题的标准解法通过动态规划递推以硬币种类为阶段金额为状态累加组合数。关键点包括二维DP\texttt{DP}DP清晰表示状态转移。注意金额为000时有一种方式什么都不用。使用long long防止溢出。该解法是动态规划入门经典题。