完全背包
时间复杂度：O(amount x amount x N)
空间复杂度：O(amount x N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func change(amount int, coins []int) int {
dp := make([][]int, len(coins)+1)
dp[0] = make([]int, amount+1)
dp[0][0] = 1
for i := 1; i <= len(coins); i++ {
dp[i] = make([]int, amount+1)
coin := coins[i-1]
for j := 0; j <= amount; j++ {
for k := 0; k*coin <= j; k++ {
dp[i][j] += dp[i-1][j-k*coin]
}
}
}
return dp[len(coins)][amount]
}
|
完全背包一维优化，即动态规划
时间复杂度：O(amount x N)
空间复杂度：O(amount)
1
2
3
4
5
6
7
8
9
10
11
12
13
| func change(amount int, coins []int) int {
dp := make([]int, amount+1)
dp[0] = 1
for i := 0; i < len(coins); i++ {
coin := coins[i]
for j := coin; j <= amount; j++ {
dp[j] += dp[j-coin]
}
}
return dp[amount]
}
|