Groupon面经

DP的优势是如果碰到如果零钱的选项里面没有1，而导致有的total不能按greedy的算法破解开的时候，如果用DP就有可能破开钱。比如total = 11, 而零钱是5， 4， 3的情况。用greedy换了一张5和一张4就换不下去了，DP可以解出一张5和两张3。

mumu007 发表于 2015-11-10 06:44
DP的优势是如果碰到如果零钱的选项里面没有1，而导致有的total不能按greedy的算法破解开的时候，如果用DP就 ...

零钱是他自定义好的。还没有遇到没法换的情况。

libralavender 发表于 2015-11-10 07:20
零钱是他自定义好的。还没有遇到没法换的情况。

我明白了，谢谢分享经验！收获很多

mumu007 发表于 2015-11-10 06:44
DP的优势是如果碰到如果零钱的选项里面没有1，而导致有的total不能按greedy的算法破解开的时候，如果用DP就 ...

还是可以greedy的，不过要有点变化。比如先换5和4， 得到［1，1］（还剩2）发现换不开3；这时退回上一级变成［1，0］（还剩6），于是得到［1，0，2］。

zhtiansweet 发表于 2015-11-13 19:25
还是可以greedy的，不过要有点变化。比如先换5和4， 得到［1，1］（还剩2）发现换不开3；这时退回上一级 ...

有道理，退回去再调整是可以的

lz是不是和HR安排的skype技术面啊？

jjwqf 发表于 2015-12-8 08:50
lz是不是和HR安排的skype技术面啊？

电话技术面试。

楼主 我看你最近也在刷题啊 要不要加个微信互相督促一起找工作啊

wendy920217 发表于 2015-12-24 16:19
楼主 我看你最近也在刷题啊 要不要加个微信互相督促一起找工作啊

私信你啦~~~

楼主， 海投多久有反应的？