房地产管理局网站,建设银行北京市分行网站,asp.net建立网站吗,山丹做网站的公司题目描述
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种硬币的数量是无…题目描述
给你一个整数数组 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
解题思路
假设给出的不同面额的硬币是[1, 2, 5]目标是 120问最少需要的硬币个数 我们要分解子问题分层级找最优子结构看到这又要晕了哈憋急~~ 下面马上举例。 这里我们使用「自顶向下」思想来考虑这个题目然后用「自底向上」的方法来解题。 dp是遍历金额总数构造的数组dp[i]: 表示总金额为 i 的时候最优解法的硬币数求dp[i]可以在dp中复用子问题解。 我们想一下求总金额 120 有几种方法下面这个思路关键了 !!! 一共有 3 种方式因为我们有 3 种不同面值的硬币。 1.拿一枚面值为 1 的硬币 总金额为 119 的最优解法的硬币数量 这里我们只需要假设总金额为 119 的最优解法的硬币数有人已经帮我们算好了 不需要纠结于此。(虽然一会也是我们自己算哈哈) 即dp[119] 1 2.拿一枚面值为 2 的硬币 总金额为 118 的最优解法的硬币数 这里我们只需要假设总金额为 118 的最优解法的硬币数有人已经帮我们算好了 即dp[118] 1 3.拿一枚面值为 5 的硬币 总金额为 115 的最优解法的硬币数 这里我们只需要假设总金额为 115 的最优解法的硬币数有人已经帮我们算好了 即dp[115] 1 因为硬币的金额已知所以dp[120]只能由这三种方法计算得到 所以总金额为 120 的最优解法就是上面这三种解法中最优的一种也就是硬币数最少 的一种我们下面试着用代码来表示一下 dp[120] Math.min(dp[119] 1, dp[118] 1, dp[115] 1); 推导出「状态转移方程」
dp[i] Math.min(dp[i - coin] 1, dp[i - coin] 1, ...)其中 coin 有多少种可能我们就需要比较多少次那么我们到底需要比较多少次呢 当然是 coins 数组中有几种不同面值的硬币就是多少次了~ 遍历 coins 数组 分别去对比即可
上面方程中的 dp[119]dp[118]dp[115] 我们继续用这种思想去分解 这就是动态规划了把这种思想思考问题的方式理解了这一类型的题目 问题都不会太大。
代码
var coinChange function(coins, amount) {let dp new Array(amount 1).fill(Infinity); // 初始化 dp 数组dp[0] 0; // 凑出金额 0 所需的硬币数为 0for (let i 1; i amount; i) { // 遍历所有金额从 1 到 amountfor (let coin of coins) { // 遍历所有硬币面额if (i - coin 0) { // 如果当前金额 i 大于等于硬币面额 coindp[i] Math.min(dp[i], dp[i - coin] 1); // 更新 dp[i] 的值}}}return dp[amount] Infinity ? -1 : dp[amount]; // 如果 dp[amount] 仍为 Infinity说明无法凑出金额
};代码分析
1. 初始化 dp 数组
let dp new Array(amount 1).fill(Infinity); // 初始化 dp 数组
dp[0] 0; // 凑出金额 0 所需的硬币数为 0dp 数组的作用dp[i] 表示凑出金额 i 所需的最少硬币数。为什么用 Infinity 初始化因为对于大多数金额我们一开始不知道需要多少硬币才能凑出所以用一个很大的数Infinity来表示“尚未计算”。dp[0] 0凑出金额 0 显然不需要任何硬币所以 dp[0] 初始化为 0。
2. 外层循环遍历所有金额
for (let i 1; i amount; i) { // 遍历所有金额从 1 到 amount作用我们需要计算从金额 1 到目标金额 amount 的每一个金额的最少硬币数。逐步计算从最小的金额开始逐步向上计算直到目标金额。这样可以确保在计算 dp[i] 时所有小于 i 的金额的最少硬币数已经计算好了。
3. 内层循环遍历所有硬币面额
for (let coin of coins) { // 遍历所有硬币面额作用对于每个金额 i我们需要考虑所有可能的硬币面额看看用哪种硬币可以更优地凑出金额 i。逐个尝试假设我们有硬币面额 [1, 2, 5]对于金额 3我们会尝试 用一枚面值为 1 的硬币然后看 dp[2] 的值。用一枚面值为 2 的硬币然后看 dp[1] 的值。用一枚面值为 5 的硬币但 3 - 5 0所以不能用。
4. 状态转移更新 dp[i]
if (i - coin 0) { // 如果当前金额 i 大于等于硬币面额 coindp[i] Math.min(dp[i], dp[i - coin] 1); // 更新 dp[i] 的值
}条件检查if (i - coin 0) 确保我们不会用一个比当前金额还大的硬币否则没有意义。状态转移逻辑 假设我们正在计算金额 i并且考虑用一枚面值为 coin 的硬币。如果我们用这枚硬币那么剩下的金额就是 i - coin凑出这个金额所需的硬币数是 dp[i - coin]。因为我们用了一枚硬币所以总硬币数是 dp[i - coin] 1。我们需要比较所有可能的硬币面额选择最小的硬币数。这就是 Math.min(dp[i], dp[i - coin] 1) 的作用。
5. 返回结果
return dp[amount] Infinity ? -1 : dp[amount]; // 如果 dp[amount] 仍为 Infinity说明无法凑出金额检查结果如果 dp[amount] 仍然是 Infinity说明我们无法用给定的硬币面额凑出目标金额 amount因此返回 -1。返回最少硬币数如果 dp[amount] 是一个有限的数说明我们成功地找到了最少硬币数直接返回它。
举例说明
假设 coins [1, 2, 5]amount 11。
初始化
dp [0, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity]
计算过程 金额 i 1 遍历硬币面额 coin 1dp[1] Math.min(Infinity, dp[0] 1) 1 结果dp [0, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 2 遍历硬币面额 coin 1dp[2] Math.min(Infinity, dp[1] 1) 2coin 2dp[2] Math.min(2, dp[0] 1) 1 结果dp [0, 1, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 3 遍历硬币面额 coin 1dp[3] Math.min(Infinity, dp[2] 1) 2coin 2dp[3] Math.min(2, dp[1] 1) 2 结果dp [0, 1, 1, 2, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 4 遍历硬币面额 coin 1dp[4] Math.min(Infinity, dp[3] 1) 3coin 2dp[4] Math.min(3, dp[2] 1) 2 结果dp [0, 1, 1, 2, 2, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 5 遍历硬币面额 coin 1dp[5] Math.min(Infinity, dp[4] 1) 3coin 2dp[5] Math.min(3, dp[3] 1) 3coin 5dp[5] Math.min(3, dp[0] 1) 1 结果dp [0, 1, 1, 2, 2, 1, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 6 遍历硬币面额 coin 1dp[6] Math.min(Infinity, dp[5] 1) 2coin 2dp[6] Math.min(2, dp[4] 1) 2coin 5dp[6] Math.min(2, dp[1] 1) 2 结果dp [0, 1, 1, 2, 2, 1, 2, Infinity, Infinity, Infinity, Infinity, Infinity] 金额 i 7 遍历硬币面额 coin 1dp[7] Math.min(Infinity, dp[6] 1) 3coin 2dp[7] Math.min(3, dp[5] 1) 2coin 5dp[7] Math.min(2, dp[2] 1) 2 结果dp [0, 1, 1, 2, 2, 1, 2, 2, Infinity, Infinity, Infinity, Infinity] 金额 i 8 遍历硬币面额 coin 1dp[8] Math.min(Infinity, dp[7] 1) 3coin 2dp[8] Math.min(3, dp[6] 1) 3coin 5dp[8] Math.min(3, dp[3] 1) 3 结果dp [0, 1, 1, 2, 2, 1, 2, 2, 3, Infinity, Infinity, Infinity] 金额 i 9 遍历硬币面额 coin 1dp[9] Math.min(Infinity, dp[8] 1) 4coin 2dp[9] Math.min(4, dp[7] 1) 3coin 5dp[9] Math.min(3, dp[4] 1) 3 结果dp [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, Infinity, Infinity] 金额 i 10 遍历硬币面额 coin 1dp[10] Math.min(Infinity, dp[9] 1) 4coin 2dp[10] Math.min(4, dp[8] 1) 4coin 5dp[10] Math.min(4, dp[5] 1) 2 结果dp [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, Infinity] 金额 i 11 遍历硬币面额 coin 1dp[11] Math.min(Infinity, dp[10] 1) 3coin 2dp[11] Math.min(3, dp[9] 1) 3coin 5dp[11] Math.min(3, dp[6] 1) 3 结果dp [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
最终结果
dp[11] 3表示凑出金额 11 所需的最少硬币数为 3。
总结
这段代码通过动态规划的思想逐步计算出每个金额的最少硬币数最终得到目标金额的最少硬币数。
