leetcode_322

Golang:

前言：这题我为了省时间空间，用了递归和map，但是没想到，还不如别人直接数组来的快，不想优化了，下次会直接用上数组。代码不推荐使用，就这样。

思路：这题是不能用贪心的，因为贪心的思路不能证明可以解这题。是的，如果确定要求最优解，除非能证明贪心可行，不然不推荐使用贪心。这题举个例子，有1元、5元，11元，f(n)表示换n元零钱需要的最小硬币数量，贪心的思路是，如果n>11，应该先用最大的，但在这个例子里，15元=11元+1元*4，贪心需要五个硬币，实际上呢，15=5元*3。动态规划的思路呢，就是f(15)=min(f(14)，f(10)，f(4))+1，注意为什么是14，10，4。因为14=15-1，10=15-5，4=15-11。

代码如下：

func coinChange(coins []int, amount int) int {
    if amount==0{
        return 0
    }
    if len(coins)==0 {
        return -1
    }
    sort.Ints(coins)
    arr:=make([]int,amount+1)
    for i:=0;i<len(coins);i++{
        if coins[i]<=amount {
            arr[coins[i]]=1
        }
    }
    return getCoinChange(coins,amount,arr)
}

func getCoinChange(coins []int, amount int,arr []int) int {
    if arr[amount]!=0 {
        return arr[amount]
    }
    if amount<coins[0] {
        arr[amount]=-1
        return -1
    }
    i:=0
    res:=amount+1
    for i<len(coins)&&coins[i]<amount{
        temp:=getCoinChange(coins,amount-coins[i],arr)
        if temp!=-1&&temp<res {
            res=temp
        }
        i++
    }
    if res==amount+1 {
        arr[amount]=-1
    }else{
        arr[amount]=res+1
    }
    return arr[amount]
}

有疑问加站长微信联系（非本文作者）