python定数量不限的硬币,币值为 25 分、10 分、5 分和 1 分,编 写代码计算 n 分有几种表示法。 (结果可能会很大,你需要将结果模上 1000000007)
时间: 2024-03-05 22:52:05 浏览: 75
好的,这是一个经典的动态规划问题。我们可以用 dp[i][j] 表示只使用前 i 种硬币,凑出 j 分钱的方案数。那么最终答案就是 dp[4][n]。转移方程如下:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
其中,coins=[1, 5, 10, 25] 表示硬币面值。初始状态为 dp[i][0]=1,即凑出 0 分钱只有一种方案,就是什么都不选。
下面是 Python 代码实现:
```
def coin_change(n):
coins = [1, 5, 10, 25]
dp = [[0] * (n+1) for _ in range(5)]
for i in range(5):
dp[i][0] = 1
for i in range(1, 5):
for j in range(1, n+1):
if j >= coins[i-1]:
dp[i][j] = (dp[i-1][j] + dp[i][j-coins[i-1]]) % 1000000007
else:
dp[i][j] = dp[i-1][j]
return dp[4][n]
```
我们可以调用 coin_change(n) 函数来计算凑出 n 分钱的方案数。例如,coin_change(10) 的返回值为 4,表示凑出 10 分钱有 4 种不同的方案。
阅读全文