硬币更改递归实现记忆了错误的值。有人可以帮忙调试吗？

Question

谁能帮我弄清楚为什么这个版本的记忆硬币找零不起作用？ 这是为了确定为目标金额进行找零的最少硬币数量。我意识到缓存输入了错误的值，并且在不使用备忘录缓存的情况下给出了正确的答案。我还能够通过不将 currNumCoins 作为参数传递给递归调用来获得一个记忆版本。我只是对为什么这个版本不起作用感到困惑。我正在将 memo 初始化为 Map<Integer, Integer> memo = new HashMap<>();

示例输入：coins = [1,2,5], targetAmount = 11 预期答案：3 实际答案：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;
}

}

Answer 1

coinChangeRecHelper 的 return-value 取决于它的三个参数（coins、currAmount 和 currNumCoins），但是 memo 缓存仅由其中一个值 (currAmount) 键控，这本质上意味着它无法准确缓存 return-value。换句话说，代码隐含地假设 coinChangeRecHelper(coins1, amount1, currAmount, currNumCoins1) == coinChangeRecHelper(coins2, amount2, currAmount, currNumCoins2)，但这是一个错误的假设。

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

是的，该方法主要通过消除缓存未考虑的不匹配参数来解决此问题。

唯一剩下的问题是coins；如果你的 coinChange 方法被不同的硬币组调用两次，它会错误地保留旧的缓存，即使它不适用于新的调用。要解决这个问题，我建议让 coinChange 创建缓存并将其作为参数传递给 coinChangeRecHelper，而不是使用实例变量。

Answer 2

每个递归都需要一个单独的 memo，这样一个递归就不会改变另一个。例如，记住使用了哪些硬币可以这样实现：

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

硬币更改递归实现记忆了错误的值。有人可以帮忙调试吗？

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

java

algorithm

recursion

memoization

coin-change