LC *322. 零钱兑换（DP）

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
}