我们先来描述一下这个问题：
给你一个代表不同面额硬币的整数数组硬币和代表总金额的整数金额。
返回弥补该金额所需的最少硬币数量。如果任何硬币组合都无法弥补该金额，则返回-1。
您可以假设您拥有无限数量的每种硬币。
例如：
或者：
或者：
此外，我们的约束之一表明 1 <=coins.length <= 12.
这个问题实际上是一个熟悉的问题，您可能在贪婪问题的背景下见过它。然而，这个版本要求我们找到
最少
数量的硬币，贪心的方法是行不通的。
neetcode 视频清楚地展示了为什么会这样：例如，如果我们的硬币是 [1, 3, 4, 5] 并且数量是 7，贪婪方法将首先得到 5，然后它会尝试所有
最大
数量，直到它必须满足两个 1，使其总数为 5、1 和 1。但是，我们可以使用比这更少的硬币：4 和 3。所以，让我们看看如何做到这一点。
我们必须以某种方式积累到我们可以使用的最小硬币数量。为此，我们从初始化一个数组开始：
我们有这个长度为 amount + 1 的数组，因为
每个索引将保存每个金额可以使用的最小硬币数量。
例如，dp 数组的索引 0 将保存我们可以使用的最小硬币数量的值使用量为0；同样，索引 7 将保存我们可以使用 7 的最小硬币数量的值。
我们用amount + 1的占位符值初始化每个索引，因为最大硬币数量不能超过amount（例如，我们可以使用7的最大硬币数量是7：1 + 1 + 1 + 1 + 1 + 1 + 1).
使用HTML,CSS,JavaScript开发Android应用程序 英文文字pdf版附源文件
如果你了解HTML，CSS和JavaScript，您已经拥有所需的工具开发Android应用程序。本动手本书展示了如何使用这些开源web标准设计和建造，可适应任何Android设备的应用程序 - 无需使用Java。您将学习如何创建一个在您选择的平台的Android友好的网络应用程序，然后转换与自由PhoneGap框架到一个原生的Android应用程序。了解为什么设备无关的移动应用是未来的潮流，并开始构建应用程序，提供更
下载
注意在这个问题中，最小价值的硬币是 1，正如约束之一所示。
对于0的数量，我们可以使用的最小硬币数量是显而易见的：0：
然后，我们将从索引 1 开始循环遍历这个数组，对于每个索引，我们将迭代硬币：
如果我们正在查看的硬币可以用于该金额（即 amountidx - coin >= 0），那么我们将更新 dp 数组中该金额的值。它将是我们已经拥有的值的最小值，或者 1 + dp[amountidx - coin]:
注意1 + dp[amountidx - coin] 的原因是我们使用已经计算出的值的解，重用子问题。所以，1 是我们目前正在考虑的硬币。
如果最后我们无法将总金额与任何硬币组合匹配，我们必须返回-1。
检查的方法是检查最后一个元素等于 amount + 1 的条件。在这种情况下，我们可以返回 -1。否则，我们将只返回包含构成金额的最小硬币数量的最后一个元素：
而且，这是最终的解决方案：
时间和空间复杂度
时间复杂度为
css">
o(n*m)o(n * m)o(n*m)
在哪里
nnn
是金额 + 1 并且
mmm
是我们拥有的硬币数量。我们迭代每个值直到 amount + 1，并且对于每个值，再次迭代每个硬币，执行恒定操作。
空间复杂度取决于我们给出的数量，因为 dp 数组的大小会随着数量的增加而增长，所以我们可以说它是
o(n)o(n)o(n)
在哪里
nnn
是金额。
是时候深呼吸了。尽管我们通常会接受动态规划问题的解决方案，但一开始就很难得到它们——不仅要提出解决方案，还要理解已经存在的解决方案。
接下来，我们来看看最大乘积子数组问题。在那之前，祝您编码愉快。
input: coins = [1, 2, 5], amount = 11
output: 3
explanation: 11 = 5 + 5 + 1
input: coins = [2], amount = 3
output: -1
input: coins = [1], amount = 0
output: 0
let dp = array.from({ length: amount + 1 }, () => amount + 1);
dp[0] = 0;
for (let amountidx = 1; amountidx < dp.length; amountidx++) {
for (const coin of coins) {
/* ... */
}
}
for (let amountidx = 1; amountidx < dp.length; amountidx++) {
for (const coin of coins) {
if (amountidx - coin >= 0) {
dp[amountidx] = math.min(dp[amountidx], 1 + dp[amountidx - coin]);
}
}
}
function coinchange(coins: number[], amount: number): number {
/* ... */
if (dp[dp.length - 1] === amount + 1) {
return -1;
}
return dp[dp.length - 1];
}
function coinChange(coins: number[], amount: number): number {
let dp = Array.from({ length: amount + 1 }, () => amount + 1);
dp[0] = 0;
for (let amountIdx = 1; amountIdx < dp.length; amountIdx++) {
for (const coin of coins) {
if (amountIdx - coin >= 0) {
dp[amountIdx] = Math.min(dp[amountIdx], 1 + dp[amountIdx - coin]);
}
}
}
if (dp[dp.length - 1] === amount + 1) {
return -1;
}
return dp[dp.length - 1];
}