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;
}

}

CodePudding user response：

The return-value of coinChangeRecHelper depends on three of its arguments (coins, currAmount, and currNumCoins), but the memo cache is keyed by only one of those values (currAmount), which inherently means that it can't accurately cache the return-value. In other words, the code implicitly assumes that coinChangeRecHelper(coins1, amount1, currAmount, currNumCoins1) == coinChangeRecHelper(coins2, amount2, currAmount, currNumCoins2), but that's a bad assumption.

I was also able to get a memoized version to work by not passing in the currNumCoins as an argument to the recursive calls.

Yes, that approach would mostly fix this issue, by eliminating a mismatched parameter that the caching doesn't account for.

The only remaining issue is coins; if your coinChange method is called twice with different sets of coins, it will erroneously retain the old cache even though it's not applicable to the new call. To fix that, I'd recommend having coinChange create the cache and pass it as an argument to coinChangeRecHelper, rather than using an instance variable.

CodePudding user response：

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);
        }
    }
}