每日算法之零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

如果没有任何一种硬币组合能组成总金额，返回 -1。

解析

我们采用自下而上的方式进行思考。仍定义 F(i)，F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i)之前，我们已经计算出 F(0)-F(i-1)的答案。 再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 F(i) 为前面能转移过来的状态的最小值加上枚举的硬币数量 1。

public class Solution {
  public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, max);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
      for (int j = 0; j < coins.length; j++) {
        if (coins[j] <= i) {
          dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
      }
    }
    return dp[amount] > amount ? -1 : dp[amount];
  }
}

转载自：

1. 零钱兑换