硬币面值组合问题

硬币面值组合问题

问题

这个题目说的是，给你一些面值不同的硬币，每一种面值的硬币都有无限多个，现在你要用这些硬币组成一个给定的数值，那么请问，总共有多少种可能的组合方式？

比如说，给你的硬币有 1 分 2 分两种面值，现在你要用它们凑 4 分钱，有以下 3 种组合方式：

4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 2 + 2

因此，要返回的答案是 3。

代码

public class AlgoCasts {

  private int coinCombination(int[] coins, int start, int sum) {
    if (sum == 0) return 1;
    if (sum < 0) return 0;
    int result = 0;
    for (int i = start; i < coins.length; ++i) {
      result += coinCombination(coins, i, sum - coins[i]);
    }
    return result;
  }

  public int numberOfCoinCombinationRecursive(int sum, int[] coins) {
    return coinCombination(coins, 0, sum);
  }

  // Time: O(n*sum), Space: O(n*sum)
  public int numberOfCoinCombinationDP(int sum, int[] coins) {
    int[][] d = new int[coins.length+1][sum+1];
    for (int i = 0; i <= coins.length; ++i) d[i][0] = 1;

    for (int i = 1; i <= coins.length; ++i) {
      for (int j = 1; j <= sum; ++j) {
        int useCurCoin = j >= coins[i-1] ? d[i][j-coins[i-1]] : 0;
        d[i][j] = d[i-1][j] + useCurCoin;
      }
    }
    return d[coins.length][sum];
  }

  // Time: O(n*sum), Space: O(sum)
  public int numberOfCoinCombinationDPOsum(int sum, int[] coins) {
    int[] d = new int[sum+1];
    d[0] = 1;

    for (int i = 1; i <= coins.length; ++i) {
      for (int j = 1; j <= sum; ++j) {
        int useCurCoin = j >= coins[i-1] ? d[j-coins[i-1]] : 0;
        d[j] = d[j] + useCurCoin;
      }
    }
    return d[sum];
  }

}