class Solution {
public:
int waysToChange(int n) {
}
};
面试题 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
说明：
注意:
你可以假设：
原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-30 21:33:49
class Solution:
def waysToChange(self, n: int) -> int:
mod = 10**9 + 7
ans = 0
for i in range(n // 25 + 1):
rest = n - i * 25
a, b = rest // 10, rest % 10 // 5
ans += (a + 1) * (a + b + 1)
return ans % mod
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-30 21:33:09
func waysToChange(n int) int {
ans := 0
mod := 1000000007
for i := 0; i * 25 <= n; i++ {
rest := n - i * 25
a, b := rest/10, rest%10/5
ans = (ans + (a + 1) * (a + b + 1) % mod) % mod
}
return ans
}
golang 解法, 执行用时: 12 ms, 内存消耗: 9.5 MB, 提交时间: 2022-11-30 21:32:46
func waysToChange(n int) int {
dp := make([]int, n + 1)
dp[0] = 1
coins := []int{1, 5, 10, 25}
for i := 0; i < 4; i++ {
for j := 1; j <= n; j++ {
if j - coins[i] >= 0 {
dp[j] += dp[j - coins[i]]
}
}
}
return dp[n] % 1000000007
}
python3 解法, 执行用时: 640 ms, 内存消耗: 64.5 MB, 提交时间: 2022-11-30 21:32:30
class Solution:
def waysToChange(self, n: int) -> int:
mod = 10**9 + 7
coins = [25, 10, 5, 1]
f = [1] + [0] * n
for coin in coins:
for i in range(coin, n + 1):
f[i] += f[i - coin]
return f[n] % mod