C语言某人想将手中的一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张,且每种票子至少一张。问:有几种换法?
时间: 2024-02-23 08:57:44 浏览: 233
编写程序,输出用一元人民币兑换成1分、2分和5分硬币共有多少种兑换方法。
这是一个经典的硬币找零问题。可以使用动态规划来解决。
定义一个二维数组dp[i][j],表示前i种面值的钞票,凑出j元钱的方案数。则状态转移方程为:
dp[i][j] = dp[i-1][j] + dp[i][j-coin[i]]
其中coin[i]表示第i种面值的钞票。
边界条件是dp[0][0] = 1,dp[i][0] = 1。
根据题目的要求,可以设置一个计数器count,记录符合要求的方案数。每当dp[4][40]更新时,count加1。最后count即为答案。
根据上述算法,可以得出答案为:21771种换法。
阅读全文