题目

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

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

思路

题目要求最值，求个数，且不需要具体的方案，想到用动态规划。

  1. dp[n] 表示凑成总金额n的所需硬币的最少个数
  3. base case:
  4.     dp[0] = 0，凑成0元所需硬币为0
  6. 状态转移：
  7.     dp[i] = 0 if n = 0
  8.     dp[i] = min(dp[i], dp[i-coin] + 1 for all coins) if n > 0
  10. 状态初始化：
  11.   dp[0] = 0, dp[1..n] = amount + 1

状态初始化设置 dp[1..n] = amount + 1 是因为如果设置为MAX_VALUE的话，更新dp值可能导致溢出。coins的最小面值为1，意味着dp[n]可能的最大值为amount，所以设为amount+1。

示例1的dp推导：

0 1 2 3 4 5 6 7 8 9 10 11
0 1 1 2 2 1 2 2 3 3 2 3

代码

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int[] dp = new int[amount+1];
  4.         // 状态初始化
  5.         dp[0] = 0;
  6.         for (int i = 1; i < dp.length; i++) {
  7.             dp[i] = amount + 1;   // 硬币面值最小为1，说明能换的硬币数最多为amount
  8.         }
  9.         // 状态转移
  10.         for (int i = 1; i < dp.length; i++) {
  11.             // 穷举所有选择, 即所有硬币
  12.             for (int coin : coins) {
  13.                 if (i < coin) {  // 当前硬币大于要换的金额，换不了，跳过
  14.                     continue;
  15.                 }
  16.                 dp[i] = Math.min(dp[i], dp[i-coin]+1);
  17.             }
  18.         }
  20.         return dp[amount] != amount + 1 ? dp[amount] : -1;
  21.     }
  22. }