题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
硬币。给定数量不限的硬币，币值为 25 分、10 分、5 分和 1 分，编写代码计算 n 分有几种表示法。(结果可能会很大，你需要将结果模上 1000000007)
示例 1:
- 输入: n = 5
- 输出：2
- 解释: 有两种方式可以凑成总金额:
- 5=5
- 5=1+1+1+1+1
示例 2:
- 输入: n = 10
- 输出：4
- 解释: 有四种方式可以凑成总金额:
- 10=10
- 10=5+5
- 10=5+1+1+1+1+1
- 10=1+1+1+1+1+1+1+1+1+1
说明：
你可以假设：
0 <= n (总金额) <= 1000000
题目思考
- 如何利用已经计算出的结果?
解决方案
思路
- 分析题目, 考虑得到 n 分的最后一枚硬币, 它可以是 25 分、10 分、5 分和 1 分
- 也就是说, 要得到 n 分的表示法, 只需要累加 n-25, n-10, n-5 以及 n-1 的方案数
- 所以我们可以利用动态规划的思路, 累加之前的结果, 求出每一分的表示方案数, 最终 n 分的方案数即为所求
- 具体做法就是, 对于每一种硬币 c, 计算从 c 到 n 分的表示方案数, 对于每个总和 sm, 都有
dp[sm]=dp[sm]+dp[sm-c] (c<=sm<=n) - 另外注意初始化 0 分的方案数为 1, 代表什么硬币都不用的情况
复杂度
- 时间复杂度
O(NC): 外层循环遍历每种硬币, 内层循环遍历总和, 所以是 N*C (C 是硬币种类数) - 空间复杂度
O(N): 使用了一个长度为 N 的数组存各个总和的方案数
代码
class Solution:
def waysToChange(self, n: int) -> int:
# 动态规划, dp[sm]存总和为sm的方案数
# 对于每一种硬币c, 都有dp[sm]=dp[sm]+dp[sm-c] (c<=sm<=n)
MOD = 1000000007
coins = [1, 5, 10, 25]
dp = [1] + [0] * n
for c in coins:
for sm in range(c, n + 1):
dp[sm] = (dp[sm] + dp[sm - c]) % MOD
return dp[n] 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号