硬币将递归更改为不同的解决方案

Question

我是递归和回溯的新手。我知道，在进行动态编程之前，我需要对这些概念完全满意。我在下面写了一个程序，可以帮助我找到给定数量n和无限数量硬币的所有可能组合。但是，我希望让我的计划为我提供不同的解决方案。我很难弄清楚如何做到这一点。

我在这里找到了一个资源：硬币更改递归使用自上而下的方法，然后对其进行修改以使用以下公式提供不同的组合：count（s，n，total）= count（s，n，total-s）[n]） 计数（S，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;
    }