[LeetCode] 322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Example 4:

Input: coins = [1], amount = 1
Output: 1

Example 5:

Input: coins = [1], amount = 2
Output: 2

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

零钱兑换。

题意是给一个数组coins表示一些零钱的面值和一个总价值amount，问如何组合能使得amount使用的硬币数量最少。若没有这样的组合就输出-1，硬币可以无限次使用。影子题983。

思路是动态规划。看了这个题目和这个题解，我算是对DP有点了解了，也搞清楚什么叫做自顶向下（记忆化搜索）和自底而上（动态规划）了。这个题既然是DP做，那么大概率就是自底而上了，也就是首先要找到DP的初始状态。这个题DP数组的定义是要达到某一个amount需要用到的最少数目的硬币数量。那么很显然 dp[0] = 0。接着看从 1 到 amount 这个范围，如果满足以下两个条件，dp[i] 就会有解了。

当前 amount - coins[j] >= 0，需要遍历每个不同的 coins，看每种不同的组合，只有当前 amount - coins[j] >= 0 的时候，才说明叠加某一个 coin 才有意义。一个反例是，如果当前amount是 5，但是coin遍历到 10，就无需操作，因为剩下的 amount < 0 了
dp[i - coins[j]] < Integer.MAX_VALUE。判断这个条件是去判断这个值 dp[i - coins[j]] 是否已经被计算过

其他的看代码就应该能懂。举个例子，11既可以 = 5 + 5 + 1，也可以 = 11 个 1 相加。这里处理的时候，因为每一个dp值都会寻求最小值，所以 5 + 5 + 1 的组合会被保留。

时间O(硬币数量 * amount)

空间O(amount)

Java实现

 1 class Solution {
 2     public int coinChange(int[] coins, int amount) {
 3         // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
 4         int[] memo = new int[amount + 1];
 5         memo[0] = 0;
 6         for (int i = 1; i <= amount; i++) {
 7             int min = Integer.MAX_VALUE;
 8             for (int j = 0; j < coins.length; j++) {
 9                 if (i - coins[j] >= 0 && memo[i - coins[j]] < min) {
10                     min = memo[i - coins[j]] + 1;
11                 }
12             }
13             memo[i] = min;
14         }
15         return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
16     }
17 }

JavaScript实现

 1 /**
 2  * @param {number[]} coins
 3  * @param {number} amount
 4  * @return {number}
 5  */
 6 var coinChange = function(coins, amount) {
 7     let memo = new Array(amount + 1);
 8     memo[0] = 0;
 9     for (let i = 1; i <= amount; i++) {
10         let min = Number.MAX_VALUE;
11         for (let j = 0; j < coins.length; j++) {
12             if (i - coins[j] >= 0 && memo[i - coins[j]] < min) {
13                 min = memo[i - coins[j]] + 1;
14             }
15         }
16         memo[i] = min;
17     }
18     return memo[amount] == Number.MAX_VALUE ? -1 : memo[amount];
19 };