package DP
import "math"
// 时间复杂度: O(n * m), 空间复杂度: O(n)
// n表示总金额amount, m表示不同面值硬币的种数
func coinChange(coins []int, amount int) int {
size := len(coins)
dp := make([]int, amount+1)
for i := 1; i <= amount; i++ {
dp[i] = math.MaxInt
}
for i := 1; i <= amount; i++ {
for j := 0; j < size; j++ {
if coins[j] > i || dp[i-coins[j]] == math.MaxInt {
continue
}
dp[i] = min(dp[i], dp[i-coins[j]]+1)
}
}
if dp[amount] == math.MaxInt {
return -1
}
return dp[amount]
}