leetcode_322

淳属虚构 · · 627 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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]
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_322

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

627 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传