# 0322. 零钱兑换

### 题目地址(322. 零钱兑换)

<https://leetcode-cn.com/problems/coin-change/>

### 题目描述

```
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

 

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0
示例 4：

输入：coins = [1], amount = 1
输出：1
示例 5：

输入：coins = [1], amount = 2
输出：2
 

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

```

### 前置知识

* 贪心算法
* [动态规划](/leetcode-solution/thinkings/dynamic-programming.md)

### 公司

* 腾讯
* 百度
* 字节
* 阿里巴巴（盒马生鲜）

### 岗位信息

* 阿里巴巴（盒马生鲜）：前端技术二面

### 思路

假如我们把 coin 逆序排列，然后从面值大的开始取，如果取了当前硬币后金额仍有小于 amount，则继续取。

举个例子：

```
eg: 对于 [1,2,5] 组成 11 块

- 排序[5,2,1]

- 取第一个5, 更新amout 为 11 - 5 = 6 (1⃣️)
      6 > 5 继续更新 为 6 - 5 = 1 (2⃣️)
      1 < 5 退出

- 取第二个2
      1 < 2 退出

- 取最后一个元素，也就是1

      1 === 1 更新为 1 - 1 = 0 (3⃣️)

- amout 为 0 退出


因此结果是 3
```

熟悉贪心算法的同学应该已经注意到了，这就是贪心算法，贪心算法想要使得 amount **尽快地变得更小**。

贪心算法通常时间复杂度更低，但对这道题目来说，贪心是不正确的！要证明它的错误，只需要随便举一个反例即可。 比如 `coins = [1, 5, 11] amout = 15`, 使用贪心就会得到错误的结果。 因此这种做法有时候不靠谱，我们还是采用靠谱的做法.

如果我们暴力求解，对于所有的组合都计算一遍，然后比较， 那么这样的复杂度是 2 的 n 次方（这个可以通过数学公式证明，这里不想啰嗦了），这个是不可以接受的。

暴力法枚举过程实际上有很多重复子问题，我们一般称重叠子问题。对于重叠子问题，我们可以使用备忘录来解决。

以 coins = \[1,2,3], amount = 6 来说，我们可以画出如下的递归树。

![](https://p.ipic.vip/3vjmts.jpg)

（图片来自<https://leetcode.com/problems/coin-change/solution/）>

如上图 F(1) 被重复计算了 13 次！！如何消除重叠子问题？答案是记忆化递归或者动态规划，二者没有本质区别。

这里以自底向上的动态规划为例讲解一下。比较容易想到的是二维数组存放 F(n) 。

定义 dp\[i]\[j] 为使用 coins 的前 j 项组成 金额 i 的最少硬币数。对于动态规划问题，最关键的是决策（不包含决策的是递推式动态规划）。对于动态规划的决策的技巧就是：仅关心最后一步和前一步，不考虑其他部分是如何达成的。

对于这道题来说，最后一步就是选择第 j 个硬币还是不选择第 j 个硬币。

* 如果选择第 j 个硬币，那么 dp\[i]\[j] = min(dp\[i]\[j - 1], dp\[i - coins\[j - 1]]\[j] + 1)

> 注意：dp\[i - coins\[j - 1]]\[j] 含义是硬币无限取， dp\[i - coins\[j - 1]]\[j - 1] 的含义就变成了硬币最多取一次

* 否则 dp\[i]\[j] = dp\[i]\[j - 1]

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount < 0:
            return - 1
        dp = [[amount + 1 for _ in range(len(coins) + 1)]
              for _ in range(amount + 1)]

        # 初始化第一行为0，其他为最大值（也就是amount + 1）
        for j in range(len(coins) + 1):
            dp[0][j] = 0

        for i in range(1, amount + 1):
            for j in range(1, len(coins) + 1):
                # 注意：dp[i - coins[j - 1]][j] 含义是硬币无限取， dp[i - coins[j - 1]][j - 1] 的含义就变成了硬币最多取一次
                if i - coins[j - 1] >= 0:
                    dp[i][j] = min(
                        dp[i][j - 1], dp[i - coins[j - 1]][j] + 1)
                else:
                    dp[i][j] = dp[i][j - 1]

        return -1 if dp[-1][-1] == amount + 1 else dp[-1][-1]
```

**复杂度分析**

* 时间复杂度：$O(amonut \* len(coins))$
* 空间复杂度：$O(amount \* len(coins))$

dp\[i]\[j] 依赖于`dp[i][j - 1]`和 `dp[i - coins[j - 1]][j] + 1)` 这是一个优化的信号，我们可以将其优化到一维。

用 dp\[i] 来表示组成 i 块钱，需要最少的硬币数，那么

1. 第 j 个硬币我可以选择不拿 这个时候， 硬币数 = dp\[i]
2. 第 j 个硬币我可以选择拿 这个时候， 硬币数 = dp\[i - coins\[j]] + 1

和 01 背包问题不同， 硬币是可以拿任意个，对于每一个 dp\[i] 我们都选择遍历一遍 coin， 不断更新 dp\[i]

### 关键点解析

* 分析出是典型的完全背包问题

### 代码

* 语言支持：JS，C++,Python3

JavaScript Code：

```js
var coinChange = function (coins, amount) {
  if (amount === 0) {
    return 0;
  }
  const dp = Array(amount + 1).fill(Number.MAX_VALUE);
  dp[0] = 0;
  for (let i = 1; i < dp.length; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (i - coins[j] >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }

  return dp[dp.length - 1] === Number.MAX_VALUE ? -1 : dp[dp.length - 1];
};
```

C++ Code：

> C++中采用 INT\_MAX，因此判断时需要加上`dp[a - coin] < INT_MAX`以防止溢出

```
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        auto dp = vector<int>(amount + 1, INT_MAX);
        dp[0] = 0;
        for (auto a = 1; a <= amount; ++a) {
            for (const auto & coin : coins) {
                if (a >= coin && dp[a - coin] < INT_MAX) {
                    dp[a] = min(dp[a], dp[a-coin] + 1);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};
```

Python3 Code:

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for j in range(len(coins)):
                if i >= coins[j]:
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1)

        return -1 if dp[-1] == amount + 1 else dp[-1]
```

**复杂度分析**

* 时间复杂度：$O(amonut \* len(coins))$
* 空间复杂度：$O(amount)$

### 扩展

这是一道很简单描述的题目， 因此很多时候会被用到大公司的电面中。

相似问题:

[518.coin-change-2](/leetcode-solution/medium/518.coin-change-2.md)


---

# Agent Instructions: 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://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/322.coin-change.md?ask=<question>
```

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.