// 完全背包;递归+记忆化搜索
// 时间 空间 O(n)
func coinChange(coins []int, amount int) int {
n := len(coins)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, amount+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int
dfs = func(i, c int) (res int) {
if i < 0 {
if c == 0 {
return 0
}
// 除 2 是防止下面 + 1 溢出
return math.MaxInt / 2
}
C := &memo[i][c]
if *C != -1 {
return *C
}
defer func() { *C = res }()
if c < coins[i] {
return dfs(i-1, c)
}
return min(dfs(i-1, c), dfs(i, c-coins[i])+1)
}
ans := dfs(n-1, amount)
if ans < math.MaxInt/2 {
return ans
}
return -1
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
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
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