硬幣變化遞回實作記憶錯誤值。有人可以幫助除錯嗎？

有人能幫我弄清楚為什么這個版本的記憶硬幣找零不起作用嗎？ 這是為了確定為目標金額找零的最小硬幣數量。我意識到快取輸入了錯誤的值，并且在不使用備忘錄快取的情況下給出了正確的答案。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;
}

}

uj5u.com熱心網友回復：

每次遞回都需要一個單獨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);
        }
    }
}

uj5u.com熱心網友回復：

的回傳值coinChangeRecHelper取決于它的三個引數（coins、currAmount和currNumCoins），但memo快取僅由其中一個值（currAmount）作為鍵，這本質上意味著它無法準確地快取回傳值。換句話說，代碼隱含地假設coinChangeRecHelper(coins1, amount1, currAmount, currNumCoins1) == coinChangeRecHelper(coins2, amount2, currAmount, currNumCoins2)，但這是一個糟糕的假設。

通過不將currNumCoins作為引數傳遞給遞回呼叫，我還能夠獲得一個記憶化的版本。

是的，該方法主要通過消除快取不考慮的不匹配引數來解決此問題。

唯一剩下的問題是coins；如果coinChange使用不同的硬幣集呼叫您的方法兩次，即使它不適用于新呼叫，它也會錯誤地保留舊快取。為了解決這個問題，我建議coinChange創建快取并將其作為引數傳遞給coinChangeRecHelper，而不是使用實體變數。

標籤：

上一篇：鏈表迭代

下一篇：前綴到后綴Java