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

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        final int INF = 0x7fffffff;
        for (int i = 1; i <= amount; i++) dp[i] = INF;
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] != INF && i + coins[j] <= amount && dp[i]!= INF)
                    dp[i + coins[j]] = Math.min(dp[i + coins[j]], dp[i] + 1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

C++ 120ms

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		const int INF = 0x7fffffff;
		vector<int> dp(amount + 1, INF);
		dp[0] = 0;
		for (int i = 0; i <= amount; i++) {
			for (int j = 0; j<coins.size(); j++) {
				if (coins[j] != INF && i + coins[j] <= amount && dp[i] != INF && dp[i + coins[j]] > dp[i] + 1)
					dp[i + coins[j]] = dp[i] + 1;
			}
		}
		return dp[amount] == INF ? -1 : dp[amount];
	}
};

python

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        INF = 0x7ffffffe
        dp = [0] + [INF] * amount 
        for i in xrange(amount + 1):
            for coin in coins:
                if i + coin <= amount:
                    dp[i+coin] = min(dp[i+coin],dp[i] + 1)
        return dp[amount] if dp[amount] != INF else -1

 

方法二：

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		const int INF = 0x7fffffff;
		vector<int> dp(amount + 1, INF);
		dp[0] = 0;
		for (int i = 0; i <= amount; i++) {
			for (int coin:coins) {
				if (i - coin >= 0 && dp[i - coin] != INF && dp[i - coin] + 1 < dp[i]) {
					dp[i] = dp[i - coin] + 1;
				}
			}
		}
		return dp[amount] == INF ? -1 : dp[amount];
	}
};