生成表示数字的组合

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

谢谢各位.我拿到了：

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 3

与您的解决方案相同，但稍微短一些，并且支持任意的分母。

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