https://leetcode.com/problems/coin-change/description/
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
- 贪心算法
假如我们把coin逆序排列，然后逐个取，取到刚好不大于amout，依次类推。
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 次方（这个可以通过数学公式证明，这里不想啰嗦了）， 这个是不可以接受的。那么我们是否可以动态规划解决呢？答案是可以，原因就是可以划分为子问题，子问题可以推导出原问题
对于动态规划我们可以先画一个二维表，然后观察，其是否可以用一维表代替。 关于动态规划为什么要画表，我已经在这篇文章解释了
比较容易想到的是二维数组：
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):
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块钱，需要最少的硬币数，那么
-
第j个硬币我可以选择不拿 这个时候， 硬币数 = dp[i]
-
第j个硬币我可以选择拿 这个时候， 硬币数 = dp[i - coins[j]] + 1
-
和背包问题不同， 硬币是可以拿任意个
-
对于每一个 dp[i] 我们都选择遍历一遍 coin， 不断更新 dp[i]
- 语言支持：JS，C++,Python3
JavaScript Code：
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:
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)$
这是一道很简单描述的题目， 因此很多时候会被用到大公司的电面中。
相似问题: