java - 生成表示数字的组合

Question

问题：

给定无限数量的 25 美分、10 美分、5 美分和 1 美分的硬币，计算表示 n 美分的方式的数量。

我的答案：

public static int generateComb(int n){
    if(n < 0){
        return 0;
    }
    if(n == 0){
        return 1;
    }

    int ways = generateComb(n-25) + generateComb(n-10) + generateComb(n-5) + generateComb(n-1);
    return ways;
}

请告诉我我的实现是否正确。

Answer 1

一种解决方法是确保没有递归调用使用的硬币大于最后使用的硬币。

Answer 2

与您的解决方案相同的方法，但稍短一些，并支持任意面额。

private static int generateComb(int amount, Collection<Integer> denominations) {
  if (amount == 0) return 1;
  if (denominations.isEmpty()) return 0;

  List<Integer> denominationsList = new ArrayList<Integer>(denominations);
  Collections.sort(denominationsList, Collections.reverseOrder());

  int currentDenomination = denominationsList.remove(0);
  int ways = 0;
  for (int total = 0; total <= amount; total += currentDenomination) {
    ways += generateComb(amount - total, denominationsList);
  }

  return ways;
}

Answer 3

谢谢大家..我能够得到它：

public static int generateComb(int n, int denom){

    int next_denom = 0;
    switch(denom){
        case 25:
            next_denom = 10;
            break;
        case 10:
            next_denom = 5;
            break;
        case 5:
            next_denom = 1;
            break;
        case 1:
            return 1;
    }

    int ways = 0;
    for(int i = 0 ; i*denom <= n ; i++){
        ways+= generateComb(n-i*denom, next_denom);
    }
    return ways;
}

Answer 4

另一种解决方案 -

int[] arr = {5, 3 , 1};
int sum = 10;
countNway(arr, sum, 0);

public int countNway(int[] arr, int sum, int start){

    if(start>arr.length){
        return 0;
    }
    if(sum==0){
        return 1;
    }
    if(sum<0){
        return 0;
    }
    int result =0;
    for(int i= start;i<arr.length;i++){
        for(int j = 1; j<=(sum/arr[i]); j++){
            result += countNway(arr, sum -arr[i]*j, i+1);
        }
    }
    return result;
}