> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/08.11-ying-bi.md).

# \[面试题 08.11]\[中等]\[动态规划]\[背包] 硬币

## 题目描述

[面试题 08.11. 硬币](https://leetcode-cn.com/problems/coin-lcci/)

硬币。给定数量不限的硬币，币值为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

## 解题思路

标准的完全背包问题, 朴素地将状态定义为`dp[i][v]`, 表示前`i`种面值的硬币构成价值为`v`的**方案数量**. 需要进行3层循环: 总面值, 硬币数量, 内部查找可能的关联位置. 本题在时间复杂度和空间复杂度上都有优化的空间, 参考[Leetcode题解: 硬币](https://leetcode-cn.com/problems/coin-lcci/solution/ying-bi-by-leetcode-solution/).

```python
class Solution:
    def waysToChange(self, n: int) -> int:
        mod = 1000000007
        coins = [25, 10, 5, 1]

        dp = [0] * (n + 1)  # 滚动数组
        dp[0] = 1  # 当总价值为0时, 不计入任何硬币可以满足, 也是一种匹配的方式, 记为1
        for coin in coins:
            for i in range(coin, n + 1):  # 对于当前coin, 比coin更小总价值的不考虑
                dp[i] = dp[i] + dp[i - coin]
        return dp[-1] % mod
```