LeetCode Q322: 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.

Solution:

Using DP.

Amount[N] = min{Amount[N-coin[1]]+1, ..., Amount[N-coin[k]]+1}

	class Solution {
	public:
	int helper(vector<int>& nums, int amount, vector<int>& coins){
	if(amount==0)
	return 0;
	int minv=INT_MAX;
	for(int i=0; i<coins.size(); i++){
	if(coins[i]>amount||nums[amount-coins[i]]==-1)
	continue;
	int v;
	if(nums[amount-coins[i]]==0){
	v=helper(nums, amount-coins[i], coins);
	v= v==-1? -1:v+1;
	}else
	v=nums[amount-coins[i]]+1;
	minv = v==-1? minv:min(minv, v);
	}
	if(minv==INT_MAX){
	nums[amount]=-1;
	return -1;
	}
	nums[amount]=minv;
	return nums[amount];
	}
	int coinChange(vector<int>& coins, int amount) {
	vector<int> nums(amount+1, 0);
	int res = helper(nums, amount, coins);
	return res;
	}
	};

view raw Q322.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int helper(vector<int>& coins, int amount, unordered_map<int, int>& myHash){
	if(amount==0){
	myHash[amount]=0;
	return 0;
	}
	if(amount<0)
	return -1;
	if(myHash[amount]!=0)
	return myHash[amount];
	int minv = INT_MAX;
	for(int i=0; i<coins.size(); i++){
	int tmp = helper(coins, amount-coins[i], myHash);
	minv = tmp==-1? minv:min(minv, tmp+1);
	}
	myHash[amount]=minv==INT_MAX? -1:minv;
	return myHash[amount];
	}
	int coinChange(vector<int>& coins, int amount) {
	if(coins.empty())
	return -1;
	if(amount==0)
	return 0;
	unordered_map<int, int> myHash;
	int res = helper(coins, amount, myHash);
	return res==INT_MAX? -1:res;
	}
	};

view raw Q322.cpp hosted with ❤ by GitHub

Round 3 solution:

	class Solution {
	public:
	int coinChange(vector<int>& coins, int amount) {
	if(amount == 0)
	return 0;
	if(coins.empty())
	return -1;
	vector<int> nums(amount+1, -1);
	for(int i=0; i<=amount; i++){
	for(int j=0; j<coins.size(); j++){
	if(i-coins[j]<0)
	continue;
	if(i-coins[j]==0){
	nums[i]=1;
	continue;
	}
	if(nums[i-coins[j]]!=-1)
	nums[i] = nums[i]==-1? nums[i-coins[j]]+1:min(nums[i], nums[i-coins[j]] + 1);
	}
	}
	return nums.back();
	}
	};

view raw Q322Rnd3.cpp hosted with ❤ by GitHub