CareerCup

DP Soln - O(N^3)

public static void main(String[] args) throws java.lang.Exception {
		int[] coins = { 1, 2, 3 };
		int[] count = { 1, 1, 3 };
		int sum = 9;
		int n = countWays(coins, count, sum);
		System.out.println(n);
	}

	/**
	 * Coin change problem with finite number of coins available denominations
	 * of coins = {1,2,3} count of coins = ={1,1,3} find the number of ways for
	 * getting change for S=6
	 */

	public static int countWays(int[] coins, int[] count, int sum) {

		int n = coins.length;
		int[][] dp = new int[sum + 1][n + 1];

		int ret = 0;
		for (int i = 1; i <= sum; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= count[j - 1]; k++) {
					if (i > coins[j - 1] * k)
						dp[i][j] += dp[i - coins[j - 1] * k][j - 1];

					if (i == coins[j - 1] * k)
						dp[i][j] += 1;

				}
			}
		}
		for (int i = 0; i <= n; i++) {
			ret += dp[sum][i]; 
		}
		return ret;
	}

based on limited knapsack problem.
public class CoinChangeLimitedSupply {
public static void main(String[] args) throws java.lang.Exception {
int[] coins = { 1, 2, 4, 8 };
int[] count = { 2, 2, 2, 2 };
int sum = 9;
int n = countWays(coins, count, sum);
System.out.println(n);
}

/**
* Coin change problem with finite number of coins available denominations
* of coins = {1,2,3} count of coins = ={1,1,3} find the number of ways for
* getting change for S=6
*/

public static int countWays(int[] coins, int[] count, int sum) {

int n = coins.length;
int[][] dp = new int[n + 1][sum + 1];

int ret = 0;
dp[0][0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = 0; i <= sum; i++) {
dp[j][i] += dp[j-1][i];
}

for (int k = 1; k <= count[j - 1]; k++) {
int initial = coins[j - 1] * k;
for (int i = initial; i <= sum; i++) {
dp[j][i] += dp[j-1][i - initial];
}
}
}

for(int i=0; i<=n; i++) {
for(int j=0; j<=sum; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println("");
}
// for (int i = 0; i <= n; i++) {
// ret += dp[i][sum];
// }
return dp[n][sum];
}
}

Top down DP. Time and space: O(number_of_coins * amount * max(count_of_coins) ).

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Coin
{
	public:
		Coin(int denom, int supply)
		{
			denom_ = denom;
			supply_ = supply;
		}
		int denom_;
		int supply_;
};

int WaysCount(vector<Coin> const &coins, int16_t amount, int16_t idx, int supply, unordered_map<uint64_t, int> &memo)
{
	if (amount < 0 ||
		idx >= coins.size() ||
		supply < 0)
	{
		return 0;
	}
	if (amount == 0) {
		return 1;
	}
	if (supply == 0) {
		++idx;
		if (idx >= coins.size()) {
			return 0;
		}
		supply = coins[idx].supply_;
	}

	uint64_t memo_key = ((((uint64_t)amount << 16) | idx) << 32) | supply;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	int count = WaysCount(coins, amount - coins[idx].denom_, idx, supply - 1, memo) +
				WaysCount(coins, amount, idx + 1, idx + 1 < coins.size() ? coins[idx + 1].supply_ : 0, memo);

	memo[memo_key] = count;
	return memo[memo_key];
}


int main()
{
	unordered_map<uint64_t, int> memo;
	vector<Coin> coins = {Coin(1, 1), Coin(2, 1), Coin(3, 3)};
	cout << WaysCount(coins, 6, 0, coins[0].supply_, memo) << "\n";
	return 0;
}

there is a pseudo polynomial algorithm for this. Basically you apply each coin n times
and mark the target value you get by adding up the number of ways you can get there.

for the sample:
dp[0][0..S] = 0
dp[0][0] = 1, base case
-- use coin with value 1
dp[1][0..S] = dp[0][0..S]
dp[1][1] = dp[0][1] + dp[0][0] + 1 = 1
-- use coin with value 2
dp[2][0..S] = dp[1][0..S]
dp[2][2] = dp[1][2] + dp[1][0] + 2 = 1
dp[2][3] = dp[1][3] + dp[1][1] + 2 = 1
-- use 1 coin with value 3
dp[3][0..S] = dp[2][0..S]
dp[3][3] = dp[2][3] + dp[2][0] + 3 = 2
dp[3][4] = dp[2][4] + dp[2][1] + 3 = 1
dp[3][5] = dp[2][5] + dp[2][2] + 3 = 1
dp[3][6] = dp[2][6] + dp[2][3] + 2 = 1
-- use 2 coins with value 3 = value 6
dp[4][0..S] = dp[2][0..S]
dp[4][6] = dp[3][6] + dp[3][0] + 6 = 2
result = dp[4][6] = 2

in c++ 11

#include <vector>
#include <iostream>

using namespace std;
typedef unsigned int uint;

unsigned int numberOfWaysForChange(const vector<pair<uint, uint>>& coins, uint S) 
{	// pair<int, int>: 1st: value, 2nd: count
	if (S < 1) return 0;
	vector<int> dpc(S + 1, 0); // current
	vector<int> dpl(S + 1, 0); // last
	dpl[0] = 1;

	for (const auto& coin : coins) {		
		for (uint value = coin.first, c = 0; c < coin.second; value += coin.first, ++c) {
			for (uint s = 0; s < S; s++) {
				if (dpl[s] == 0) continue;
				dpc[s] = dpl[s];
				if (s + value > S) continue;
				dpc[s + value] = dpl[s + value] + dpl[s];
			}
			swap(dpl, dpc);
		}
	}
	return dpl.back();
}

int main()
{
	cout << numberOfWaysForChange({ {1,1},{2,1},{3,3} }, 6) << endl;
}