javaalgorithmrecursionmemoizationcoin-change

Coin change recursive implementation memoizing wrong values. Could someone help debug?


Could someone help me figure out why this version of the memoized coin change doesn't work? This is to determine the minimum number of coins to make change for a target amount. I realize that the cache is putting in the wrong values and without using the memo cache this gives the right answer. I was also able to get a memoized version to work by not passing in the currNumCoins as an argument to the recursive calls. I'm just stumped to why this version doesn't work. I'm initializing memo as Map<Integer, Integer> memo = new HashMap<>();

Example input: coins = [1,2,5], targetAmount = 11 Expected Answer : 3 Actual Answer: 7

class Solution {    
Map<Integer, Integer> memo = new HashMap<>();

public int coinChange(int[] coins, int amount) {
    return coinChangeRecHelper(coins, amount, amount, 0);
}

public int coinChangeRecHelper(int[] coins, int amount, int currAmount, int currNumCoins) {
    if (currAmount < 0) {
        return -1;
    }
    
    if (currAmount == 0) {
        //return 0;
        return currNumCoins;
    }
    
    if (memo.containsKey(currAmount)) {
        return memo.get(currAmount);
    }
    
    int minCoins = Integer.MAX_VALUE;
    for (int i = 0; i < coins.length; i++) {
        int currCoin = coins[i];
        int numCoinsTmp = coinChangeRecHelper(coins, amount, currAmount - currCoin, currNumCoins + 1);
        if (numCoinsTmp != -1) {
            minCoins = Math.min(minCoins, numCoinsTmp);
        }
    }
    if (minCoins == Integer.MAX_VALUE) {
        minCoins = -1;
    }

    memo.put(currAmount, minCoins);
    return minCoins;
}

}


Solution

  • You need a separate memo for each recursion so one does not change the other. For example memorizing which coins where used can be achieved like so:

    import java.util.HashMap;
    import java.util.Map;
    
    public class Solution {
    
        private Map<Integer, Integer> memo;
    
        public int coinChange(int[] coins, int amount) {
            memo = new HashMap<>();
            return coinChangeRecHelper(coins, amount, amount, 0, new HashMap<Integer,Integer>());
        }
    
        public int coinChangeRecHelper(int[] coins, int amount, int currAmount, int currNumCoins, Map<Integer, Integer> coinQty ) {
    
            if (currAmount < 0) return -1;
    
            if (currAmount == 0) {
                memo = coinQty;
                return currNumCoins;
            }
    
            int minCoins = Integer.MAX_VALUE;
            for (int currCoin : coins) {
                Map<Integer, Integer> coinQtyCopy = new HashMap<>(coinQty);
                coinQtyCopy.putIfAbsent(currCoin, 0);
                coinQtyCopy.put(currCoin, coinQtyCopy.get(currCoin)+1);
                int numCoinsTmp = coinChangeRecHelper(coins, amount, currAmount - currCoin, currNumCoins + 1, coinQtyCopy);
                if (numCoinsTmp != -1) {
                    minCoins = Math.min(minCoins, numCoinsTmp);
                }
            }
    
            if (minCoins == Integer.MAX_VALUE) {
                minCoins = -1;
            }
    
            return minCoins;
        }
    
        public Map<Integer, Integer> getMemo() {
            return memo;
        }
    
        public static void main(String[] args) {
    
            Solution s = new Solution();
            System.out.println(s.coinChange(new int[]{1,2,5}, 11) + " coins used: ");
    
            for(int coin : s.getMemo().keySet()) {
                System.out.println( s.getMemo().get(coin)+ " of " + coin);
            }
        }
    }