Рекурсия по обмену монет Все решения на разные решения

Question

Я новичок в рекурсии и возврата. Я знаю, что должен полностью освоиться с этими концепциями, прежде чем перейти к динамическому программированию. Ниже я написал программу, которая помогает мне найти все возможные комбинации для заданного количества n и неограниченного количества монет. Однако я хочу, чтобы моя программа дала мне отличные решения. Мне трудно понять, как это сделать.

Я нашел ресурс здесь: Изменение монеты, которое рекурсивно использует нисходящий подход, а затем модифицирует его, чтобы дать различные комбинации, используя следующую формулу: count (s, n, total) = count (s, n, total-s[n]) + количество (с, n-1, всего)

Это говорит о том, что я рекурсивно использую значение, а затем рекурсивно, исключая значение и уменьшая монеты на 1.

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

В любом случае, любая помощь по поводу того, как я могу преобразовать свою программу для печати отдельных решений и как она работает, будет очень полезна.

public class Recursive {

    static int[] combo = new int[100];
    public static void main(String argv[]) {
        int n = 8;
        int[] amounts = {1, 5, 10};
        ways(n, amounts, combo, 0, 0, 0);
    }

    public static void  ways(int n, int[] amounts, int[] combo, int count, int sum, int index) {
        if(sum == n) {
            printArray(combo, index);
        }

        if(sum > n) {
            return;
        }


        for(int i=0;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, 0, sum, index + 1);
            sum = sum - amounts[i];
        }
    }

    public static void printArray(int[] combo, int index) {
        for(int i=0;i < index; i++) {
            System.out.print(combo[i] + " ");
        }
        System.out.println();
    }
}

Фактическое количество неделимых действительных комбинаций для сумм {1, 2, 5} и N = 10 составляет 128 с использованием чисто рекурсивного исчерпывающего метода (код ниже).

Мой вопрос заключается в том, можно ли улучшить поиск с помощью запоминания / динамического программирования. Если так, как я могу изменить алгоритм ниже, чтобы включить такие методы.

Answer 1

Простые модификации позволяют избежать повторов.

Использовать отсортировано amounts массив.
Начальное значение цикла должно исключать предыдущие значения из amounts,
я использовал count аргумент (кажется, не используется)

 for(int i=count;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, i, sum, index + 1);
            sum = sum - amounts[i];
        }

Answer 2

static HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public static void main(String argv[]) {
        int n = 1000;
        System.out.println(getSteps(n, 0,0 ));
    }

    public static int getSteps(int n, int sum, int count) {

        if(n == sum) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        if(memo.containsKey(sum)) {
            return memo.get(sum);
        }
        for(int i=1; i<=3;i++) {
            sum = sum + i;
            count += getSteps(n, sum, 0);
            sum = sum - i;
            memo.put(sum, count);
        }
        return count;
    }