322.零钱兑换

动态规划

自底向上，计算1~amount每个数作为结果所需要的最小硬币数量。

时间复杂度：O(Sn)，其中 SS 是金额，nn 是面额数
空间复杂度：O(S)

func coinChange(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    
    dp := make([]int, amount + 1)
    dp[0] = 0
    for i := 1; i < amount+1; i++ {
        dp[i] = amount + 1
    }

    // 计算1~amount的每种情况下所需硬币数
    for i := 1; i <= amount; i++{
        for _, coin := range coins {
            //硬币面额大于amount则跳过
            if coin <= i {
                // 求最小dp[i-coin]
                if dp[i] > dp[i-coin] + 1{
                    dp[i] = dp[i-coin] + 1
                }
            }
        }
    }

    if dp[amount] == amount + 1 {
        return -1
    } else {
        return dp[amount]
    }
}