最小硬币组合

最小硬币组合

问题

这个题目说的是，给你一些面值不同的硬币，每一种面值的硬币都有无限多个，现在你要用这些硬币组成一个给定的数值，那么请问，最少需要多少个硬币。另外，如果给你的面值无法组成给定数值，就返回 -1。

比如说，给你的硬币有 1 分 2 分两种面值，现在你要用它们凑 4 分钱。

我们知道用 1 分 2 分凑 4 分有 3 种组合：

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

其中使用了最少硬币的组合是 2 + 2，用了两个硬币，于是要返回的答案就是 2。

代码

public class AlgoCasts {

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

    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]] : Integer.MAX_VALUE;
        if (useCurCoin != Integer.MAX_VALUE) useCurCoin += 1;
        d[i][j] = Math.min(d[i-1][j], useCurCoin);
      }
    }
    return d[coins.length][sum] == Integer.MAX_VALUE ? -1 : d[coins.length][sum];
  }

  // Time: O(n*sum), Space: O(sum)
  public int minCoinCombinationOsum(int[] coins, int sum) {
    int[] d = new int[sum+1];
    for (int j = 1; j <= sum; ++j)
      d[j] = Integer.MAX_VALUE;

    for (int i = 1; i <= coins.length; ++i) {
      for (int j = coins[i-1]; j <= sum; ++j) {
        if (d[j-coins[i-1]] != Integer.MAX_VALUE) {
          d[j] = Math.min(d[j], d[j-coins[i-1]] + 1);
        }
      }
    }
    return d[sum] == Integer.MAX_VALUE ? -1 : d[sum];
  }

}