-
Notifications
You must be signed in to change notification settings - Fork 3
/
_0322_CoinChange.java
140 lines (128 loc) · 3.91 KB
/
_0322_CoinChange.java
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
package com.diguage.algorithm.leetcode;
import java.util.*;
/**
* = 322. Coin Change
*
* https://leetcode.com/problems/coin-change/[Coin Change - LeetCode]
*
* 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 2:
* [source]
* ----
* Input: coins = [1, 2, 5], amount = 11
* Output: 3
* Explanation: 11 = 5 + 5 + 1
* ----
*
* .Example 2:
* [source]
* ----
* Input: coins = [2], amount = 3
* Output: -1
* ----
*
* *Note:*
*
* You may assume that you have an infinite number of each kind of coin.
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-01-26 22:16
*/
public class _0322_CoinChange {
/**
* Runtime: 91 ms, faster than 6.13% of Java online submissions for Coin Change.
*
* Memory Usage: 42.7 MB, less than 5.33% of Java online submissions for Coin Change.
*
* Copy from: https://leetcode.com/problems/coin-change/solution/[Coin Change solution - LeetCode]
*/
public int coinChange(int[] coins, int amount) {
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int current, int[] count) {
if (current < 0) {
return -1;
}
if (current == 0) {
return 0;
}
if (count[current - 1] != 0) {
return count[current - 1];
}
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, current - coin, count);
if (0 <= res && res < min) {
min = res + 1;
}
}
count[current - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[current - 1];
}
/**
* Runtime: 427 ms, faster than 5.00% of Java online submissions for Coin Change.
*
* Memory Usage: 115.5 MB, less than 5.33% of Java online submissions for Coin Change.
*/
public int coinChangeDpWithMemo(int[] coins, int amount) {
int count = dpWithMemo(coins, new HashMap<>(), amount, amount);
if (count > amount) {
return -1;
}
return count;
}
public int dpWithMemo(int[] coins, Map<Integer, Integer> memo, int amount, int current) {
if (current == 0) {
return 0;
}
if (current < 0) {
return amount;
}
List<Integer> counts = new ArrayList<>();
for (int coin : coins) {
int newCoin = current - coin;
int count;
if (memo.containsKey(newCoin)) {
count = memo.get(newCoin);
} else {
count = dpWithMemo(coins, memo, amount, newCoin) + 1;
memo.put(newCoin, count);
}
counts.add(count);
}
return Collections.min(counts);
}
/**
* Time Limit Exceeded
*/
public int coinChangeDp(int[] coins, int amount) {
int count = dp(coins, amount, amount);
if (count > amount) {
return -1;
}
return count;
}
private int dp(int[] coins, int amount, int current) {
if (current == 0) {
return 0;
}
if (current < 0) {
return amount;
}
List<Integer> counts = new ArrayList<>();
for (int coin : coins) {
counts.add(dp(coins, amount, current - coin) + 1);
}
return Collections.min(counts);
}
public static void main(String[] args) {
_0322_CoinChange solution = new _0322_CoinChange();
int[] c1 = {1, 2, 5};
int r1 = solution.coinChange(c1, 11);
System.out.println((r1 == 3) + " : " + r1);
int[] c2 = {2};
int r2 = solution.coinChange(c2, 3);
System.out.println((r2 == -1) + " : " + r2);
}
}