leetcode Coin Change

leetcode Coin Change

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

题目地址 : leetcode Coin Change

题意:

零钱兑换,让你用最少的零钱数换取目标的数量。如有零钱1,2,5,换成11最少的为5+5+1 ,3个硬币

思路:

dp,设dp[i] 为兑换目标i最少的硬币数。

则有:dp[i + coins[j] ] = min(dp[i + coins[j] ] , dp[i] + 1)

或者 dp[i] = min(dp[i – coins[j]] + 1,dp[i])

说白了就是用当前的硬币能组合成啥,取最小。

第一个A此题=v= 水啊~

 

Code

java 22ms

C++ 120ms

python 

 

方法二:

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Coin Change
本文地址:https://www.hrwhisper.me/leetcode-coin-change/

您的支持将鼓励我继续创作!

Leetcode , , . permalink.

5 thoughts on “leetcode Coin Change

    • You are right.
      I just guess the max number will not greater than 0x7ffffffe(2147483646), so if the number greater than it(2147483647), it wil be overflow.
      Now, I use 0x7fffffff(2147483647) as maximum number, and add dp[i]!= INF for condition judge.
      Thanks~

Leave a Reply

Your email address will not be published. Required fields are marked *