Рекурсия изменения монет Все решения для различных решений

Question

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

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

Это говорит о том, что я рекурсив используюзначение и затем рекурсивно, исключая значение и уменьшая монеты на 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

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

Answer 2

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

Использовать отсортированный массив 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];
        }