UVa 357 Let Me Count The Way

题目描述

Mel\texttt{Mel}Mel在大商场购物后收到171717美分找零：111枚101010美分、111枚555美分和222枚111美分。当天晚些时候，他在便利店购物，又收到171717美分找零：222枚555美分和777枚111美分。他开始思考：“有多少种不同的硬币组合可以组成171717美分？”经过一番思考，他得出答案是666种。现在他要求你考虑一般情况。

编写程序，计算用美国硬币（111美分、555美分、101010美分、252525美分、505050美分）组成给定金额的不同组合数。

输入格式

输入包含一组000到300003000030000之间的整数，每行一个。

输出格式

对于每个输入值，输出相应语句：

• 如果有多种组合：There are m ways to produce n cents change.
• 如果只有111种组合：There is only 1 way to produce n cents change.

样例输入

17 11 4

样例输出

There are 6 ways to produce 17 cents change. There are 4 ways to produce 11 cents change. There is only 1 way to produce 4 cents change.

题目分析

问题的本质

这是一个经典的硬币找零问题（coin change problem\texttt{coin change problem}coin change problem），属于完全背包问题：给定几种面额的硬币（每种无限供应），求组成特定金额的不同组合数。

硬币种类

• Penny\texttt{Penny}Penny（111美分）
• Nickel\texttt{Nickel}Nickel（555美分）
• Dime\texttt{Dime}Dime（101010美分）
• Quarter\texttt{Quarter}Quarter（252525美分）
• Half-dollar\texttt{Half-dollar}Half-dollar（505050美分）

数据范围

金额最大为300003000030000，硬币种类为555种。使用动态规划可以在O(5×30000)O(5 \times 30000)O(5×30000)的时间内预处理所有结果。

组合与排列的区别

本题要求的是组合数（不考虑硬币顺序），而不是排列数。例如，用111美分和555美分组成666美分：

• 组合：1+51+51+5（只有一种）
• 排列：1+51+51+5和5+15+15+1（两种）

动态规划中的完全背包通常计算的是组合数（通过限制外层循环为硬币种类）。

解题思路

步骤一：动态规划状态定义

设dp[i][j]dp[i][j]dp[i][j]表示使用前iii种硬币组成金额jjj的组合数。

步骤二：状态转移方程

对于硬币种类iii，面额为cic_ici​：

• 不使用第iii种硬币：dp[i−1][j]dp[i-1][j]dp[i−1][j]
• 使用第iii种硬币（至少一枚）：dp[i][j−ci]dp[i][j - c_i]dp[i][j−ci​]

因此：
dp[i][j]=dp[i−1][j]+dp[i][j−ci] dp[i][j] = dp[i-1][j] + dp[i][j - c_i]dp[i][j]=dp[i−1][j]+dp[i][j−ci​]

步骤三：初始化

dp[0][0]=1dp[0][0] = 1dp[0][0]=1（用000种硬币组成000金额有111种方式）

步骤四：空间优化

可以使用一维数组，但需要按硬币顺序正向遍历（完全背包）：

for(intcoin:cents)for(intj=coin;j<=MAX;j++)ways[j]+=ways[j-coin];

但注意：一维正向遍历计算的是组合数（因为硬币按顺序添加，避免重复计算不同顺序）

步骤五：预处理

由于n≤30000n \leq 30000n≤30000，可以预先计算所有金额的结果，然后直接查表输出。

参考代码

// Let Me Count The Ways// UVa ID: 357// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){vector<int>cents={1,5,10,25,50};// 二维 DP 数组：dp[i][j] 表示用前 i 种硬币组成金额 j 的组合数longlongintways[6][30010]={0};ways[0][0]=1;// 边界条件// 动态规划预处理for(inti=1;i<=5;i++)// 枚举硬币种类for(intj=0;j<=30000;j++){// 不使用第 i 种硬币ways[i][j]=ways[i-1][j];// 使用至少一枚第 i 种硬币if(j-cents[i-1]>=0)ways[i][j]+=ways[i][j-cents[i-1]];}intn;while(cin>>n){if(ways[5][n]==1)cout<<"There is only 1 way to produce "<<n<<" cents change."<<endl;elsecout<<"There are "<<ways[5][n]<<" ways to produce "<<n<<" cents change."<<endl;}return0;}