[leetcode]322. Coin Change找零钱

待我称王封你为后i 2021-11-11 01:34 742阅读 0赞

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:

  1. Input: coins = [1, 2, 5], amount = 11
  2. Output: 3 
  3. Explanation: 11 = 5 + 5 + 1

Example 2:

  1. Input: coins = [2], amount = 3
  2. Output: -1

题意：

给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个

1402496-20190521080029794-701018117.png

要amount为11，我们当然可以这样：

1402496-20190521080052643-707532212.png

但要求amount为11，且硬币数量最少，那么答案应该是：

1402496-20190521080213630-1693348042.png --> 返回最少硬币数量为3

Solution1

转载于:https://www.cnblogs.com/liuliu5151/p/9075030.html

发表评论

表情：
评论列表 （有 0 条评论，742人围观）

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

相关阅读