C语言编程邮局现有5角、8角、1元三种面值的邮票,一个顾客邮寄物品需要邮资为12元,问邮递员用这三种邮票给出12元邮资有多少种方法(可以只出现1域2种邮票)。
时间: 2023-06-01 19:02:48 浏览: 355
这是一道典型的动态规划问题。我们可以定义一个二维数组dp[i][j],其中i表示使用前i种邮票,j表示凑出j元邮资的方案数。则有状态转移方程:
dp[i][j] = dp[i-1][j] + dp[i][j-面值i]
其中dp[i-1][j]表示不使用第i种邮票,dp[i][j-面值i]表示使用第i种邮票。
最终答案为dp[3][12],即使用前3种邮票凑出12元邮资的方案数。
具体实现请见下方代码:
阅读全文