题目
思路
经典DP。
dp[i]：兑换i最少需要多少个硬币。 确定基本状态：dp[0] = 0 状态转移：想要得到amount需要的最少硬币，如果知道了dp[amount-1]的数量，那dp[amount]即为dp[amount-1] 1（加上一个一元的硬币），然后遍历coins，找到需要硬币数最少的那个硬币。
代码语言：javascript复制func coinChange(coins []int, amount int) int {
sort.Ints(coins)
dp := make([]int, amount 1)
for i := range dp {
dp[i] = amount 1
}
dp[0] = 0
for i := 1; i < len(dp); i {
for _, v := range coins {
if i < v {
break
}
dp[i] = min(dp[i], 1 dp[i-v])
}
}
if dp[amount] == amount 1 {
return -1
}
return dp[amount]
}
func min(i, j int) int {
if i > j {
return j
}
return i
}
