Количество способов подменить монету

Question

Я пытаюсь решить проблему обмена монет, используя памятку и рекурсию. Но в моем коде есть что-то сбойное, это дает мне неправильный вывод.

    public static int coinChangeMemo(int coins[], int n) {
        int [][] memo = new int[n+1][coins.length+1];
        for (int row = 0; row < memo.length; row++) {
            for (int col = 0; col < memo[row].length; col++) {
                memo[row][col] =-1; 
            } 
        }
        return coinChangeMemoHelper(coins, n, 0, memo);
    }


    private static int coinChangeMemoHelper(int coins[], int n, int index, int memo[][]) {
        if(n == 0) {
            return 1;
        }
        if(index >= coins.length) {
            return 0;
        }
        if(n <= 0) {
            return 0;
        }

        if(memo[n][index] != -1) {
            return memo[n][index];
        }
        int withUsingCurrent = coinChangeMemoHelper(coins, n-coins[0], index, memo);
        int withoutUsingCurrent  = coinChangeMemoHelper(coins, n, index+1, memo);

        memo[n][index] = withUsingCurrent + withoutUsingCurrent;
        return withUsingCurrent + withoutUsingCurrent;

    }

    public static void main(String[] args) {
        //coins denominations are 1, 2

        int coins[] = {1,2};
        //i want a change of 4 
        int sum = 4;

        System.out.println(coinChangeMemo(coins, sum));

Монеты достоинством в наличии 1,2

Я хочу сумму 4.

Возможные пути:

1. (1,1,1,1)
2. (1,2,1)
3. (2,2)

Я ожидаю выхода 3, но он возвращает мне 5

Answer 1

Вам необходимо внести 2 изменения в свой код: -> 1.Вы можете объединить последние 2 базовых варианта как: if (index == coins.length || n <0) {return 0;} 2.Вы сделали ошибку в рекурсивном вызове withUsingCurrent: ОБНОВИТЕ ЭТО, КАК ЭТО НИЖЕ, внизу int withUsingCurrent = coinChangeMemoHelper (coins, n-coins [index], index, memo); </p>