322. 零钱兑换（JS实现）

柔情只为你懂 2022-11-28 00:21 219阅读 0赞

## 1 题目 ##

> 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。  
> 示例 1:  
> 输入: coins = \[1, 2, 5\], amount = 11  
> 输出: 3  
> 解释: 11 = 5 + 5 + 1  
> 示例 2:  
> 输入: coins = \[2\], amount = 3  
> 输出: -1

链接：https://leetcode-cn.com/problems/coin-change

## 2 思路 ##

**这道题考察贪心+回溯算法，我们先把硬币排序，然后构造一棵树，先从大面值的硬币开始，逐级相减，直到总金额为0，即找到了目标的最优组合，题解中还可以用动态规划的方法来做**

## 3代码 ##

/** * @param {number[]} coins * @param {number} amount * @return {number} */
    var coinChange = function(coins, amount) { 
      coins.sort((a,b) => a-b);
    
      if (amount === 0) return 0;
      if (amount < coins[0]) return -1;
    
      let ans = 999999;
      d(amount, coins.length - 1, 0, coins);
    
    
      function d(num, index, len, coins) { 
        if (num === 0) { 
          ans = Math.min(ans, len);
          return;
        };
        if (index < 0) return;
    
        for (let k=Math.floor(num / coins[index]); k >=0 && k + len < ans; k--) { 
            d(num - coins[index] * k, index - 1, len + k, coins);
        }
      }
    
      return ans === 999999 ? -1 : ans;
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode322.零钱兑换

//322.零钱兑换 if 0 /* 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额...

小灰灰/ 2024年04月18日 08:24/ 0 赞/ 91 阅读

相关 322. 零钱兑换

322. 零钱兑换题干分析解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如何初始化

阳光穿透心脏的1/2处/ 2023年10月16日 17:04/ 0 赞/ 17 阅读

相关 322. 零钱兑换

题目： [322. 零钱兑换][322.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

╰半夏微凉°/ 2023年07月13日 05:57/ 0 赞/ 28 阅读

相关 Leetcode 322. 零钱兑换

Leetcode 322. 零钱兑换 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

曾经终败给现在/ 2023年02月14日 03:06/ 0 赞/ 47 阅读

相关 322. 零钱兑换（JS实现）

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

柔情只为你懂/ 2022年11月28日 00:21/ 0 赞/ 220 阅读

相关（js）leetcode 322. 零钱兑换

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

Love The Way You Lie/ 2022年10月26日 11:29/ 0 赞/ 186 阅读

相关 322. 零钱兑换

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

忘是亡心i/ 2022年10月09日 12:17/ 0 赞/ 217 阅读

相关 Leetcode 322. 零钱兑换

题目重述给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何

秒速五厘米/ 2022年09月11日 15:18/ 0 赞/ 213 阅读

相关 LeetCode-322. 零钱兑换

[322. 零钱兑换][322.] 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币

小咪咪/ 2022年01月27日 00:25/ 0 赞/ 242 阅读

相关 322.零钱兑换

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

淩亂°似流年/ 2021年06月22日 15:38/ 0 赞/ 396 阅读