想问一道关于里口的改版题

最近在准备面试，看到有道题和里口 三二二 差不多，问题是给你一个代表美元的数值， 然后告诉你欧元的汇率是1.3， 然后欧元的coins 有这些

500 bill, 200 bill, 100 bill, 50 bill, 20 bill, 10 bill, 5 bill, 2 bill, 1 bill, 50 cents, 25 cents, 10 cents, 5 cents, 2 cents, 1 cent.

还是问最少需要的硬币。 一开始我想用memo table + bottom up，但后来发现这个会有小数所以table index不好处理， 后来想用greedy但不确定能不能用。。求指导。。

可以把小数和整数分离。比如24.456.则可以分别解决24和456.
如果不相信目测该组数是canonical。则用DP也不会太差。用BFS+memo也可以。
我觉得针对你给出的数字，会大胆使用贪心。

14417335 发表于 2019-2-1 01:29
可以把小数和整数分离。比如24.456.则可以分别解决24和456.
如果不相信目测该组数是canonical。则用DP也不 ...

感谢感谢，还有请问怎样判断能不能用贪心呢。。网上找了下解释发现也不是很清楚，，