-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCoinChange.java
More file actions
75 lines (59 loc) · 1.89 KB
/
CoinChange.java
File metadata and controls
75 lines (59 loc) · 1.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class CoinChange {
public static int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount <= 0) return 0;
// create dp array
int[] minCoins = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
minCoins[i] = Integer.MAX_VALUE;
// Try each coin
for (int coin : coins) {
if (coin <= i && minCoins[i-coin] != Integer.MAX_VALUE) {
minCoins[i] = Math.min(minCoins[i], 1 + minCoins[i-coin]);
}
}
}
// if (minCoins[amount] == Integer.MAX_VALUE) return -1;
return minCoins[amount] == Integer.MAX_VALUE ? -1 : minCoins[amount];
}
public static void main(String[] args) {
int[] coins1 = {1,2,5};
int amount1 = 11;
System.out.println(coinChange(coins1, amount1));
System.out.println();
int[] coins2 = {2};
int amount2 = 3;
System.out.println(coinChange(coins2, amount2));
// -1
}
}
/*
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
1, 5, 6, 9; amount = 11
amount:
0: no coins
1: 1 coin
2: 2 coins: remainder 1 (1 from 1, plus 1 for 2)
3: 1 of 1, plus 2 from 2; 3
4: coin 1, remain 3; 3 from 3 plus 1 for 4
5: coin 5 or 1; 1x1: rem = 4; 1x5 rem = 0; min = 1 coin 5
6: coin 6 or 5 or 1
store min # coins to get to all amounts
*/