4.26Amazon视频面试：coin change的变种

孙行者 发表于 2019-4-29 05:19
这题还是要backtrack方法+贪婪法。动态法可能有解，但是那玩意不是普遍使用。

想请教一下 greedy 怎么加？ 如过是单纯的从大的开始往后找，找到后就停止，那结果可能会不对。 比如这个例子 [1, 6, 7], [5, 2, 1], 12。 一般的backtrack 代码很简单，就是有点慢。

chenyijia055 发表于 2019-5-4 00:42
没看懂 你这里为什么是 dp = min(dp, num + dp) 而不是 dp = min(dp, j + dp)
还有这里是 for i in reve ...

没看懂你为什么认为我该按你的思路写代码。

你要是有测试样例证明我的代码有错，敬请分享。
你要是一眼看出什么逻辑错误，请指正。
你要是看出我的代码和你熟知的模版不同，想知道它们的异同，也得给出链接吧？

和那个声称greedy的一样(不认为有greedy解)，要准备面试的话，不能光说不练，show me your code。

tinlittle 发表于 2019-5-5 02:39
没看懂你为什么认为我该按你的思路写代码。

你要是有测试样例证明我的代码有错，敬请分享。

你的代码漏洞百出，整个逻辑都是错误的。另外，你的test cases写得也是烂的不行，自己去拿这些test cases好好想想你为什么错，( [1, 6, 7], [5, 2, 1], 13),  ([1, 2, 5], [3, 3, 1], 12), ([1, 2, 5], [3, 3, 1], 13), ([1, 2, 5], [3, 3, 1], 1), 第一次没想直接给你指出来，你还来劲了。

下面是我的code.
class Solution:
    def coin_change(self, coins, nums, amount):
      self.res= float('inf')
      d  = {c:n for c, n in zip(coins, nums)}
      def dfs(curr, count):
        if curr == amount:
          self.res = min(self.res, count)
          return
        for nxt in d:
          if nxt +curr <= amount and d[nxt] >= 1:
            d[nxt] -= 1
            dfs(curr+nxt, count+1)
            d[nxt] += 1
      dfs(0, 0)
      return self.res if self.res != float('inf') else -1


补充内容 (2019-5-5 14:55):
[1, 6, 7], [5, 2, 1], 1 再多送你一个简单的,你就懂为什么这么问了。

点个赞。刷题，收集面经中。。

看楼上几位吵得热闹，给楼主提个建议吧，coin change这类问题总归还是背包问题的经典衍生，所以万变不离其宗，楼主可以搜一下背包九讲，基础背包问题概括的挺全了

补充内容 (2019-5-15 16:44):
其实一个想法很简单：如果每种硬币只有一个，那么怎么解决？在这个条件下，如果有些硬币的面值可以相同呢？

tinlittle 发表于 2019-4-29 08:09
这题在322的解之上再加一层每一枚coin的总数的循环就好了，因为coin数不是无限的，哪个针对amount的循环要 ...

python代码真是简洁有力。还有几个月就要秋招了，想转python刷题，请问您觉得可行吗？推荐吗？目前是java刷题，各种api都比较熟悉了。

chenyijia055 发表于 2019-5-5 14:45
你的代码漏洞百出，整个逻辑都是错误的。另外，你的test cases写得也是烂的不行，自己去拿这些test cases ...

我也觉得那个solution有问题，关键为什么下面还有人点赞。。。

chenyijia055 发表于 2019-5-5 14:45
你的代码漏洞百出，整个逻辑都是错误的。另外，你的test cases写得也是烂的不行，自己去拿这些test cases ...

看着回溯的dfs
好似夕阳下的奔跑
那是我逝去的青春
awsl

想问一下dfs可以解吗？层数=硬币种类，每一层一个for循环增加该种硬币的数目，限制条件就是该种硬币的个数&不超过target值，保存合适的结果。返回条件是硬币种类都遍历完了。，最好硬币能够从大到小排好，这样dfs分只能少一点。这样可以吗？

我来说两种方法：

1. coins全部加上id, coin[i]是这个coin的面值。DP[i][j] 是如果用这个coin能达到j钱数的最小coin数。dp[i][j] = dp[i-1][j-coin[i]] == 0 ? 0 : Math.min(dp[i-1][j-1], dp[i-1][j-coin[i]] + 1)

2. BFS (Dijkstra) 如果amount比较大，coin的面值也比较大，可以用BFS，从0出发，queue里放入目前的amount，和剩下的零钱的数量。