Coin change problem

Approach

• Input is #

Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
 
public class Solution {
    public static void main(String[] args) {
        /* Save input */
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int [] coins = new int[m];
        for (int i = 0; i < m; i++) {
            coins[i] = scan.nextInt();
        }
        scan.close();
 
        System.out.println(numWays(n, coins));
    }
    
    public static long numWays(int n, int [] coins) {
        if (n < 0) {
            return 0;
        }
        return numWays(n, coins, 0, new HashMap<String, Long>());
    }
    
    public static long numWays(int n, int [] coins, int coinNumber, HashMap<String, Long> cache) {
        /* Check our cache */
        String key = n + "," + coinNumber;
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        /* Base case */
        if (coinNumber == coins.length - 1) {
            if (n % coins[coinNumber] == 0) {
                cache.put(key, 1L);
                return 1;
            } else {
                cache.put(key, 0L);
                return 0;
            }
        }
        /* Recursive case */
        long ways = 0;
        for (int i = 0; i <= n; i += coins[coinNumber]) {
            ways += numWays(n - i, coins, coinNumber + 1, cache);
        }
        /* Cache and return solution */
        cache.put(key, ways);
        return ways;
    }
}
 

• method overriding used for recursive function
• input amount required, coins available with infinite supply
• output number of ways denomination can be arranged

Python

class Solution:
	def coinChange(self, coins, amount: int) -> int:
		dp = [amount + 1] * (amount + 1)
		dp = [amount + 1] (float("inf"))
		print(dp)
		dp[0] = 0
 
		for a in range(1, amount + 1):
			for c in coins:
				if a - c >= 0:
					dp[a] = min(dp[a], 1 + dp[a - c])
 
		return dp[amount] if dp[amount] != amount + 1 else - 1
 
sol = Solution()
coins = [1,2,5]
amt = 7
print(sol.coinChange(coins, amt))

Javascript

memoization

const coinChange = function(coins, amount, memo = {}) {
    if (amount === 0) return 0; // Base case: if amount is 0, return 0
    
    if (amount < 0) return -1; // Base case: if amount is negative, return -1
    
    if (memo[amount] !== undefined) return memo[amount]; // If result is already memoized, return it
    
    let minCoins = Infinity; // Initialize minCoins with Infinity
    
    for (const coin of coins) {
        const remainingAmount = amount - coin;
        const result = coinChange(coins, remainingAmount, memo);
        if (result >= 0 && result < minCoins) {
            minCoins = result + 1;
        }
    }
    
    memo[amount] = minCoins === Infinity ? -1 : minCoins; // Memoize the result
    
    return memo[amount]; // Return the result
};
 
// Example usage:
const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount)); // Output: 3 (11 = 5 + 5 + 1)
 

tabulation

const coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // Base case: 0 coins needed to make amount 0
    
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] === Infinity ? -1 : dp[amount];
};
 
// Example usage:
const coins = [1, 2, 5];
const amount = 11;
console.log(coinChange(coins, amount)); // Output: 3 (11 = 5 + 5 + 1)
 

Questions

• task Q. Why was amount multiplied amt + 1 number of times, why is the grid initialed with max value? is used as an initial placeholder value because it’s greater than any possible valid answer so this can also go as INFINITY