> For the complete documentation index, see [llms.txt](https://imhuay.gitbook.io/studies/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/leetcode0322-zhong-deng-ling-qian-dui-huan.md).
# 零钱兑换
 [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/pages/R5NyOzkn3qAZy7wCx1pS#中等) [](/studies/algorithms.md#leetcode) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/pages/R5NyOzkn3qAZy7wCx1pS#动态规划) [](https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/pages/R5NyOzkn3qAZy7wCx1pS#暴力递归与动态规划)
**问题简述**
```
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
```
> [322. 零钱兑换 - 力扣（LeetCode）](https://leetcode-cn.com/problems/coin-change/)
**思路：完全背包**
* 定义 `dfs(a)` 表示凑成金额 `a` 需要的最少硬币数；
* **递归基**：1）显然 `dfs(0) = 0`；2）当 `a` 小于币值时，返回无穷大，表示无效结果；
Python：递归
```python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
from functools import lru_cache
N = len(coins)
@lru_cache(maxsize=None)
def dfs(a):
if a == 0: return 0
if a < 0: return float('inf')
ret = float('inf')
for i in range(N):
if a >= coins[i]:
ret = min(ret, dfs(a - coins[i]) + 1)
return ret
ret = dfs(amount)
return -1 if ret == float('inf') else ret
```
Python：动态规划 写法1）根据递归过程改写
```python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
N = len(coins)
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for i in range(N):
if a >= coins[i]:
dp[a] = min(dp[a], dp[a - coins[i]] + 1)
return -1 if dp[-1] == float('inf') else dp[-1]
```
Python：动态规划 写法2）先遍历“物品”，在遍历“容量”
关于先后遍历两者的区别见[完全背包 - 代码随想录](https://programmercarl.com/背包问题理论基础完全背包.html)，本题中没有区别；
```python
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
N = len(coins)
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(N):
for a in range(coins[i], amount + 1):
dp[a] = min(dp[a], dp[a - coins[i]] + 1)
return -1 if dp[-1] == float('inf') else dp[-1]
```
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://imhuay.gitbook.io/studies/algorithms/problems/2022/06/leetcode0322-zhong-deng-ling-qian-dui-huan.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.