Coin Chain Problem — Total number of ways to get the denomination of coins.
1 min readMar 27, 2019
By Recursion
private static int findMinWays(int[] coins, int amount, int currentcoin) {
if (amount == 0) {
return 1;
}
if (amount < 0) return 0;
int ways = 0;
for (int i = currentcoin; i < coins.length; i++) {
ways += findMinWays(coins, amount - coins[i], i);
}
return ways;
}
Another Way recursion
static int minWaysAnotherWay(int coins[], int coinsLeng, int total, String way) {
if (total == 0) return 1;
if (total < 0) return 0;
if (coinsLeng <= 0 && total >= 1) return 0;
return minWaysAnotherWay(coins, coinsLeng - 1, total, "way1")
+ minWaysAnotherWay(coins, coinsLeng, total - coins[coinsLeng - 1], "way2");
}
Dynamic Programing
private static int minWayDP(int[] coins, int amount) {
int m[] = new int[amount + 1];
m[0] = 1;
for (int i = 0; i < coins.length; i++) {
for (int j = coins[i]; j <= amount; j++) {
m[j] += m[j - coins[i]];
}
}
return m[amount];
}