Coin Change

题目描述：

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

思路:

背包问题，得出递推公式d p[n] = min(dp[coins[0],coins[1]….])+1

代码:

func coinChange(coins []int, amount int) int {
     n := len(coins)
    if amount == 0{
        return 0
    }
    var ans []int
    ans = make([]int, amount+1)
    for i:=1;i<=amount;i++{
        minNum := 99999
        for j:=0;j<n;j++{
            if coins[j] <= i {
                if ans[i-coins[j]] == 0 && i != coins[j]{
                    continue
                }
                minNum = min(minNum, ans[i-coins[j]]) 
            }
        }
        if minNum != 99999 {
            ans[i] = minNum+1
        }
    }
    
    if ans[amount] == 0{
        return -1
    }
    return ans[amount]
}

func min(a, b int)int{
    if a>b {
        return b
    }else{
        return a
    }
}

代码效率：

执行用时：12 ms, 在所有 Go 提交中击败了55.09%的用户
内存消耗：6.3 MB, 在所有 Go 提交中击败了93.82%的用户