回溯最小选项，通过递归使用1、5和7求和一个数字

Question

我想创建一个递归函数，返回使用数字1、5和7创建特定数字的最小选项（固定预定数字）。重要的是，这只是由没有循环的递归完成的。

例如：

如果n=10，则该方案由5 5给出，即2个数字，因此这是最小值，这是我们将得到的结果（与7 1 1或5 1 1相反，它是4或6个更长的选项）。

如果n=6，那么我们得到的结果是2（因为它是15的和）。

如果n=5（或7或1），那么我们得到的结果是1（因为它只由数字给出）。

class TEST { 

static int countMin( int S[], int m, int n ,int min) 
    { 
        if (n == 0) 
            return 1;      
        if (n < 0) 
            return 0; 
        if (m <=0 && n >= 1) 
            return 0; 
        return Math.min(min,countMin( S, m - 1, n ,min-1) + countMin( S, m, n-S[m-1],min-1 )); 
    } 

public  static int f(int n)  {
      int arr[] = {1, 5, 7};  
      return countMin(arr, arr.length, n,n);
} 

    public static void main(String[] args) 
    { 
        int n = 10;
        System.out.println("The number "+n+ " - " + f(n) + " minimum options to create");
        int n2 = 7;
        System.out.println("The number "+n2+ " - " + f(n2) + " minimum options to create"); 
        int n3 = 6;
        System.out.println("The number "+n3+ " - " + f(n3) + " minimum options to create");

    } 

} 

对于n=10和n=5，我得到正确的结果，但对于n=6，我得不到正确的结果，n=6应该返回2。

*我使用了以下链接：https://www.geeksforgeeks.org/coin-change-dp-7/

Answer 1

设想一棵树，其中每个节点都有一个值，并且有3个子节点，其值分别递减7、5和1

因此，节点总数为15的子节点的值为8、10、14

我们可以从第一个节点开始，计算每个级别，当我们发现一个值为0的孩子时停止。如果一个子节点的值小于0，我们也会停止查看它。

例如，对于10：

                10
            /    |    \
        3        5       9
      / | \    / | \   / | \
    -4 -2 2   -2 0 4   2 4 1

我们在2号深度发现了0号

private static int calculate(int total, int depth) {
    if (total == 0)
        return depth;
    else {
        int i = total - 7  >= 0 ? calculate(total - 7, depth+1) : Integer.MAX_VALUE;
        int j = total - 5  >= 0 ? calculate(total - 5, depth+1) : Integer.MAX_VALUE;
        int k = total - 1  >= 0 ? calculate(total - 1, depth+1) : Integer.MAX_VALUE;
        return Collections.min(Arrays.asList(i, j, k));
    }
}

这

int n = 10;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 7;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 6;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 18;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");

输出这个

The number 10 - 2 minimum options to create
The number 7 - 1 minimum options to create
The number 6 - 2 minimum options to create
The number 18 - 4 minimum options to create

编辑：同样的时髦的lambda风格：

private static int calculate(int total, int depth) {
    return total == 0 ? 
        depth : 
        Stream.of(7, 5, 1)
              .map(i -> total - i  >= 0 ? calculate(total - i, depth+1) : Integer.MAX_VALUE)
              .min(Integer::compare)
              .get();
}