322.coin-change.md

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回  -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

---

题目可以类比完全背包问题

N = coins.length    // 物品个数为硬币种类数
V = amount          // 背包体积相当于总金额
v[N] = [1,1,...,1] // 所有物品体积为1
w[N] = coins       // 物品价值为硬币面值

完全背包代码模板

for i=0; i< N; i++; // N个物品
    for j = v[i]; j <= V; j++; // 背包体积（从小到大）
        dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i])
return dp[V]

动态规划求解

dp[i]表示价值 i 需要的最少硬币数

状态转换方程

dp[j] = Math.min(dp[j], dp[j - v[i]] + 1)

多代码实现

class Solution {
    public int coinChange(int[] coins, int V) {
        int f[] = new int[V + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int c : coins) {
            for (int i = c; i <= V; i++){
                f[i] = Math.min(f[i], f[i - c] + 1);
            }
        }
        return f[V] == 0x3f3f3f3f? -1: f[V];
    }
}

cpp

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int max = amount + 1;
        vector<int> dp(amount+ 1, max);
        dp[0] = 0;
        for (int i = 0; i< coins.size(); i++){
            for (int j = 1; j<= amount; j++){
                if (j < coins[i]) continue;
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == max ? -1: dp[amount];
    }
};

javascript

var coinChange = function (coins, amount) {
  let MAX = Number.MAX_SAFE_INTEGER;
  let dp = new Array(amount + 1).fill(MAX); // dp[i] 表示价值i需要的最少硬币数
  dp[0] = 0;
  for (let i = 0; i < coins.length; i++) {
    // 循环物品
    for (let j = 1; j <= amount; j++) {
      // 循环体积
      if (j - coins[i] < 0) continue;
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); // 最少方案数
    }
  }
  return dp[amount] == MAX ? -1 : dp[amount];
};

golang

func coinChange(coins []int, amount int) int {
    max := amount+1
    dp := make([]int, amount+1)
    for i:=0; i<=amount; i++{
        dp[i] = max
    }
    dp[0] = 0
    for i:=0; i< len(coins);i++ {
        for j :=1; j<= amount; j++{
            if j - coins[i] < 0 {
                continue
            }
            if dp[j - coins[i]] + 1 < dp[j] {
                dp[j] = dp[j - coins[i]] + 1
            }
        }
    }
    if dp[amount] == max{
        return -1
    }
    return dp[amount]
}