# Coin Change

Medium

## 完全背包问题：不限个数 + 目标装满 + 求最少硬币数

You are given coins of different denominations and a total amount of money amount. Write a function to compute 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`.
Example 1:
Input:
coins =
[1, 2, 5]
, amount =
11
Output:
3
Explanation:
11 = 5 + 5 + 1
Example 2:
Input:
coins =

, amount =
3
Output:
-1
Note: You may assume that you have an infinite number of each kind of coin.

## Analysis

• 每个元素可以取任意次；
• 只问最小的硬币数，就类似于 climbing stairs，只靠 sum 一个维度就可以了，但是循环依然是两层。

## Solution

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

public class Solution {
public int coinChange(int[] coins, int amount) {
// dp[n] = min number of coins to make amount n;
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp = 0;
for(int j = 0; j < coins.length; j++){
for(int i = coins[j]; i <= amount; i++){
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
Another implementation

class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
int MAX = Integer.MAX_VALUE;
// dp[i] = min number of coins to make amount i;
int dp[] = new int[amount + 1];
dp = 0;
for (int j = 1; j <= amount; j++) {
dp[j] = MAX;
for (int i = 0; i < coins.length; i++) {
if (j >= coins[i] && dp[j - coins[i]] != MAX) {
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
if (dp[amount] == MAX) {
return -1;
}
return dp[amount];
}
}
LeetCode Official Solution - Dynamic Programming
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;
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];
}
}
DFS Recursive + Memoization
F(S) - minimum number of coins needed to make change for amount `S` using coin denominations `[c0 … cn−1]`
Then:
F(S)=F(S−C)+1
Recursion Search Tree: // [1, 2, 5] target = 6
// rec (6) // rec(6 - 1), rec(6 - 2), rec(6 - 5) // rec(6 - 1 - 1), rec(6 - 1 - 2), rec(6 - 1 - 5), rec(6 - 2 - 1), rec(6 - 5 - 1) // ... // rec(0) = 0

`minCount[]` - A memo to record visited & min coins for amount `i`
• if `minCount[i] == -1`, visited, but not reachable
• if `minCount[i] == MAX`, not visited
class Solution {
private static int MAX;
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
// A memo to record visited & min coins for amount i
int[] minCount = new int[amount + 1];
MAX = amount + 1;
Arrays.fill(minCount, MAX);
int min = coinChanger(coins, amount, minCount);
return min;
}
// minimum number of coins to sum to `amount`, if impossible, return -1
private int coinChanger(int[] coins, int amount, int[] minCount) {
if (amount == 0) {
return 0;
}
if (minCount[amount] != MAX) {
return minCount[amount];
}
int min = MAX;
for (int i = 0; i < coins.length; i++) {
if (amount >= coins[i]) {
int tmp = coinChanger(coins, amount - coins[i], minCount);
if (tmp != -1 && tmp < MAX) {
min = Math.min(min, tmp + 1);
}
}
}
minCount[amount] = min == MAX ? -1 : min;
return minCount[amount];
}
}
The difference is that if you update`dp`while:
• increasing `i` then the previous partial result `dp[i - coin]` is the result that has considered `coin` already
• decreasing `i` then the previous partial result `dp[i - coin]` is the result that has not considered `coin` yet
/**
* @return number of ways to make sum s using repeated coins
*/
public static int coinrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp = 1;
for (int coin : coins)
for (int i = coin; i <= s; i++)
dp[i] += dp[i - coin];
return dp[s];
}
/**
* @return number of ways to make sum s using non-repeated coins
*/
public static int coinnonrep(int[] coins, int s) {
int[] dp = new int[s + 1];
dp = 1;
for (int coin : coins)
for (int i = s; i >= coin; i--)
dp[i] += dp[i - coin];
return dp[s];
}