题目
代码
零钱兑换
dp[i]表示可以凑成总金额i所需的最少的硬币个数，
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
| func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := 1; i < len(dp); i++ {
dp[i] = amount + 1
}
for i := 1; i <= amount; i++ {
for _, v := range coins {
if i-v >= 0 {
dp[i] = min(dp[i], dp[i-v]+1)
}
}
}
if dp[len(dp)-1] == amount+1 {
return -1
}
return dp[len(dp)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
|
零钱兑换II
dp[i]表示可以凑成总金额i的硬币组合数，参考零钱兑换，可以写出这样的代码：
1
2
3
4
5
6
7
8
9
10
11
| for i := 1; i < len(dp); i++ {
for _, v := range coins {
if i-v >= 0 {
if dp[i-v] == 0 {
dp[i]++
} else {
dp[i] += dp[i-v]
}
}
}
}
|
但这样会有重复，比如coins = [1,2,5]，计算dp[3]的时候，dp[3-1]+1和dp[3-2]+2的结果都被考虑了进去，所以需要另辟蹊径。
可以先考虑coin=1的情况，算出dp[1]~dp[amount]，再考虑下一枚硬币，这样就不会有重复。
1
2
3
4
5
6
7
8
9
10
| func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for _, coin := range coins {
for i := coin; i <= amount; i++ {
dp[i] += dp[i-coin]
}
}
return dp[amount]
}
|
复杂度
时间复杂度：O（len(coins)*amount）
空间复杂度：O（amount）