-
Notifications
You must be signed in to change notification settings - Fork 0
/
Coin-Change.go
105 lines (92 loc) · 1.79 KB
/
Coin-Change.go
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
package coinchange
import (
"math"
)
func min(a, b int) int {
if a > b {
return b
}
return a
}
var memo = map[int]int{}
func dp(coins []int, n int) int {
// 查詢備忘錄 避免重複
if _, vok := memo[n]; vok {
return memo[n]
}
if n == 0 {
return 0
}
if n < 0 {
return -1
}
res := math.MaxInt
for _, coin := range coins {
subproblem := dp(coins, n-coin)
if subproblem == -1 {
continue
}
res = min(res, 1+subproblem)
}
if res != math.MaxInt {
memo[n] = res
} else {
memo[n] = -1
}
return memo[n]
}
// 備忘錄 遞迴 時間複雜O(kn).
func CoinChangeMemoryTableRecursion(coins []int, amount int) int {
memo = map[int]int{}
return dp(coins, amount)
}
// dp array 迭代解法
func CoinChangeDP(coins []int, amount int) int {
dp := make([]int, amount+1)
dp[0] = 0
// 初始化, 湊成 amount 金額的硬幣 最多就 amount 個(全都用1元), 所以 amount+1相當於正的無窮
// dp[]的定義: 當目標金額為i時, 至少需要dp[i]枚硬幣湊出
for i := 1; i < len(dp); i++ {
dp[i] = amount + 1
}
// 外層 for 循環遍歷所有狀態的所有取值
for i := 1; i <= amount; i++ {
// 內層 for 循環遍歷求所有選擇的最小值
for _, coin := range coins {
if i-coin < 0 {
continue
}
// 狀態轉移
dp[i] = min(dp[i], 1+dp[i-coin])
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
func CoinChange(coins []int, n int) int {
var dpClosure func(n int) int
dpClosure = func(n int) int {
if n == 0 {
return 0
}
if n < 0 {
return -1
}
res := math.MaxInt
for _, coin := range coins {
subproblem := dpClosure(n - coin)
if subproblem == -1 {
continue
}
res = min(res, 1+subproblem)
}
if res != math.MaxInt {
return res
} else {
return -1
}
}
return dpClosure(n)
}