600字范文,内容丰富有趣,生活中的好帮手!
600字范文 > python【力扣LeetCode算法题库】面试题 08.11- 硬币

python【力扣LeetCode算法题库】面试题 08.11- 硬币

时间:2023-12-16 18:22:27

相关推荐

python【力扣LeetCode算法题库】面试题 08.11- 硬币

面试题 08.11. 硬币

硬币。给定数量不限的硬币,币值为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 = 25a + 10b + 5c + d的非负整数解的数量。

注意到25, 10, 5均为5的倍数,令n = 5m + k, 0 <= k <= 4,

得到:5m = 25a + 10b + 5c + (d-k)

令e = (d-k)/5,显然e必为整数,且与d一一对应。

则原方程解的数量等于m = 5a + 2b + c + e的解的数量, 记为F(m)。

考虑a的取值。

当a = 0时,相当于求方程m = 2b + c + e的非负整数解的数量。

若b = i&

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。