8000 322. Coin Change · kimi0230/LeetcodeGolang@a8754f1 · GitHub
[go: up one dir, main page]
Skip to content

Commit a8754f1

Browse files
kimi0230kimi0230
committed
322. Coin Change
1 parent 862bf32 commit a8754f1

File tree

4 files changed

+289
-0
lines changed

4 files changed

+289
-0
lines changed

‎Leetcode/0322.Coin-Change/Coin-Change.go

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package coinchange
2+
3+
import (
4+
"math"
5+
)
6+
7+
func min(a, b int) int {
8+
if a > b {
9+
return b
10+
}
11+
return a
12+
}
13+
14+
var memo = map[int]int{}
15+
16+
func dp(coins []int, n int) int {
17+
// 查詢備忘錄 避免重複
18+
if _, vok := memo[n]; vok == true {
19+
return memo[n]
20+
}
21+
22+
if n == 0 {
23+
return 0
24+
}
25+
26+
if n < 0 {
27+
return -1
28+
}
29+
30+
res := math.MaxInt
31+
for _, coin := range coins {
32+
subproblem := dp(coins, n-coin)
33+
if subproblem == -1 {
34+
continue
35+
}
36+
res = min(res, 1+subproblem)
37+
}
38+
if res != math.MaxInt {
39+
memo[n] = res
40+
} else {
41+
memo[n] = -1
42+
}
43+
return memo[n]
44+
}
45+
46+
// 備忘錄 遞迴 時間複雜O(kn).
47+
func CoinChangeMemoryTableRecursion(coins []int, amount int) int {
48+
return dp(coins, amount)
49+
}
50+
51+
// dp array 迭代解法
52+
func CoinChangeDP(coins []int, amount int) int {
53+
dp := make([]int, amount+1)
54+
dp[0] = 0
55+
56+
// 初始化, 湊成 amount 金額的硬幣 最多就 amount 個(全都用1元), 所以 amount+1相當於正的無窮
57+
for i := 1; i < len(dp); i++ {
58+
dp[i] = amount + 1
59+
}
60+
61+
// 外層 for 循環遍歷所有狀態的所有取值
62+
for i := 1; i <= amount; i++ {
63+
// 內層 for 循環遍歷球所有選擇的最小值
64+
for _, coin := range coins {
65+
if i-coin < 0 {
66+
continue
67+
}
68+
dp[i] = min(dp[i], 1+dp[i-coin])
69+
}
70+
}
71+
if dp[amount] > amount {
72+
return -1
73+
}
74+
75+
return dp[amount]
76+
}

‎Leetcode/0322.Coin-Change/Coin-Change_test.go

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package coinchange
2+
3+
import (
4+
"testing"
5+
)
6+
7+
var tests = []struct {
8+
arg1 []int
9+
arg2 int
10+
want int
11+
}{
12+
{
13+
[]int{1, 2, 5},
14+
11,
15+
3,
16+
},
17+
}
18+
19+
func TestCoinChangeDP(t *testing.T) {
20+
for _, tt := range tests {
21+
if got := CoinChangeDP(tt.arg1, tt.arg2); got != tt.want {
22+
t.Errorf("got = %v \n want = %v \n", got, tt.want)
23+
}
24+
}
25+
}
26+
27+
func TestCoinChangeMemoryTableRecursion(t *testing.T) {
28+
for _, tt := range tests {
29+
if got := CoinChangeMemoryTableRecursion(tt.arg1, tt.arg2); got != tt.want {
30+
t.Errorf("got = %v \n want = %v \n", got, tt.want)
31+
}
32+
}
33+
}
34+
35+
var arg1 = []int{1, 2, 5}
36+
var arg2 = 11
37+
38+
func BenchmarkCoinChangeDP(b *testing.B) {
39+
b.ResetTimer()
40+
for i := 0; i < b.N; i++ {
41+
CoinChangeDP(arg1, arg2)
42+
}
43+
}
44+
45+
func BenchmarkCoinChangeMemoryTableRecursion(b *testing.B) {
46+
b.ResetTimer()
47+
for i := 0; i < b.N; i++ {
48+
CoinChangeMemoryTableRecursion(arg1, arg2)
49+
}
50+
}
51+
52+
/*
53+
go test -benchmem -run=none LeetcodeGolang/Leetcode/0322.Coin-Change -bench=.
54+
goos: darwin
55+
goarch: amd64
56+
pkg: LeetcodeGolang/Leetcode/0322.Coin-Change
57+
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
58+
BenchmarkCoinChangeDP-8 13531378 91.60 ns/op 96 B/op 1 allocs/op
59+
BenchmarkCoinChangeMemoryTableRecursion-8 50481345 21.66 ns/op 0 B/op 0 allocs/op
60+
PASS
61+
ok LeetcodeGolang/Leetcode/0322.Coin-Change 2.459s
62+
*/

‎Leetcode/0322.Coin-Change/README.md

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,137 @@
1+
# [322. Coin Change](https://leetcode.com/problems/coin-change/)
2+
`Medium`
3+
## 題目
4+
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
5+
6+
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.
7+
8+
You may assume that you have an infinite number of each kind of coin.
9+
10+
11+
12+
Example 1:
13+
14+
Input: coins = [1,2,5], amount = 11
15+
Output: 3
16+
Explanation: 11 = 5 + 5 + 1
17+
Example 2:
18+
19+
Input: coins = [2], amount = 3
20+
Output: -1
21+
Example 3:
22+
23+
Input: coins = [1], amount = 0
24+
Output: 0
25+
26+
27+
Constraints:
28+
29+
1 <= coins.length <= 12
30+
1 <= coins[i] <= 231 - 1
31+
0 <= amount <= 104
32+
33+
34+
## 題目大意
35+
給妳 k 種面值的硬幣, 面值分別為 c1,c2 ...,ck, 每種硬幣的數量無限.
36+
再給你一個總金額. 求出**最少** 需要幾枚硬幣湊出這個金額, 如果不能湊出 return -1.
37+
38+
## 解題思路
39+
`dp(n)` 的定義: 輸入一個目標金額n, 返回湊出目標金額n的最少硬幣數量
40+
41+
## 來源
42+
* https://books.halfrost.com/leetcode/ChapterFour/0300~0399/0322.Coin-Change/
43+
* https://leetcode.com/problems/coin-change/
44+
45+
## 解答
46+
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0322.Coin-Change/Coin-Change.go
47+
48+
```go
49+
package coinchange
50+
51+
import (
52+
"math"
53+
)
54+
55+
func min(a, b int) int {
56+
if a > b {
57+
return b
58+
}
59+
return a
60+
}
61+
62+
var memo = map[int]int{}
63+
64+
func dp(coins []int, n int) int {
65+
// 查詢備忘錄 避免重複
66+
if _, vok := memo[n]; vok == true {
67+
return memo[n]
68+
}
69+
70+
if n == 0 {
71+
return 0
72+
}
73+
74+
if n < 0 {
75+
return -1
76+
}
77+
78+
res := math.MaxInt
79+
for _, coin := range coins {
80+
subproblem := dp(coins, n-coin)
81+
if subproblem == -1 {
82+
continue
83+
}
84+
res = min(res, 1+subproblem)
85+
}
86+
if res != math.MaxInt {
87+
memo[n] = res
88+
} else {
89+
memo[n] = -1
90+
}
91+
return memo[n]
92+
}
93+
94+
// 備忘錄 遞迴 時間複雜O(kn).
95+
func CoinChangeMemoryTableRecursion(coins []int, amount int) int {
96+
return dp(coins, amount)
97+
}
98+
99+
// dp array 迭代解法
100+
func CoinChangeDP(coins []int, amount int) int {
101+
dp := make([]int, amount+1)
102+
dp[0] = 0
103+
104+
// 初始化, 湊成 amount 金額的硬幣 最多就 amount 個(全都用1元), 所以 amount+1相當於正的無窮
105+
for i := 1; i < len(dp); i++ {
106+
dp[i] = amount + 1
107+
}
108+
109+
// 外層 for 循環遍歷所有狀態的所有取值
110+
for i := 1; i <= amount; i++ {
111+
// 內層 for 循環遍歷球所有選擇的最小值
112+
for _, coin := range coins {
113+
if i-coin < 0 {
114+
continue
115+
}
116+
dp[i] = min(dp[i], 1+dp[i-coin])
117+
}
118+
}
119+
if dp[amount] > amount {
120+
return -1
121+
}
122+
123+
return dp[amount]
124+
}
125+
```
126+
127+
```shell
128+
go test -benchmem -run=none LeetcodeGolang/Leetcode/0322.Coin-Change -bench=.
129+
goos: darwin
130+
goarch: amd64
131+
pkg: LeetcodeGolang/Leetcode/0322.Coin-Change
132+
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
133+
BenchmarkCoinChangeDP-8 13531378 91.60 ns/op 96 B/op 1 allocs/op
134+
BenchmarkCoinChangeMemoryTableRecursion-8 50481345 21.66 ns/op 0 B/op 0 allocs/op
135+
PASS
136+
ok LeetcodeGolang/Leetcode/0322.Coin-Change 2.459s
137+
```

‎README.md

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -303,6 +303,20 @@
303303
<th> O(n) </th>
304304
<th> O(n) </th>
305305
</tr>
306+
<!-- 0322 -->
307+
<tr>
308+
<th> 0322</th>
309+
<th> Dynamic Programming </th>
310+
<th>
311+
<a href="https://leetcode.com/problems/coin-change/"> Coin Change </a>
312+
</th>
313+
<th>
314+
<a href="https://github.com/kimi0230/LeetcodeGolang/tree/master/Leetcode/0322.Coin-Change"> Go </a>
315+
</th>
316+
<th> Medium </th>
317+
<th> </th>
318+
<th> </th>
319+
</tr>
306320
<!-- 0509 -->
307321
<tr>
308322
<th> 0509</th>

0 commit comments

Comments
 (0)
0