找零钱dp的问题# JobHunting - 待字闺中
i*y
1 楼
请问找零钱最少的问题，如果找不出怎么办，比如没有1cent只有2cent的面值，一般这
样的问题该怎么处理呢？
opt[3] =opt[3-2]+1;
可是没1cent然后咋办？设opt[1] = max_value?
样的问题该怎么处理呢？
opt[3] =opt[3-2]+1;
可是没1cent然后咋办？设opt[1] = max_value?
k*y
2 楼
def solve_coin_change_dp(coins, value):
"""A dynamic solution to the coin change problem with optimal solution"""
solution = [None for x in range(value + 1)]
solution[0] = []
for i in range(1, value + 1):
for coin in coins:
if coin > i: continue
elif not solution[i] or len(solution[i - coin]) + 1 < len(
solution[i]):
if solution[i - coin] != None:
solution[i] = solution[i - coin][:]
solution[i].append(coin)
if solution[-1] != None:
#print '%d coins: %s' % (len(solution[-1]), solution[-1]) + "for " +
str(value)
return solution[-1]
我的DP 代码，请看看
【在 i****y 的大作中提到】
: 请问找零钱最少的问题，如果找不出怎么办，比如没有1cent只有2cent的面值，一般这
: 样的问题该怎么处理呢？
: opt[3] =opt[3-2]+1;
: 可是没1cent然后咋办？设opt[1] = max_value?
"""A dynamic solution to the coin change problem with optimal solution"""
solution = [None for x in range(value + 1)]
solution[0] = []
for i in range(1, value + 1):
for coin in coins:
if coin > i: continue
elif not solution[i] or len(solution[i - coin]) + 1 < len(
solution[i]):
if solution[i - coin] != None:
solution[i] = solution[i - coin][:]
solution[i].append(coin)
if solution[-1] != None:
#print '%d coins: %s' % (len(solution[-1]), solution[-1]) + "for " +
str(value)
return solution[-1]
我的DP 代码，请看看
【在 i****y 的大作中提到】
: 请问找零钱最少的问题，如果找不出怎么办，比如没有1cent只有2cent的面值，一般这
: 样的问题该怎么处理呢？
: opt[3] =opt[3-2]+1;
: 可是没1cent然后咋办？设opt[1] = max_value?
s*p
3 楼
为什么所有的解法都只给出最小值，而不给出具体的怎么找的解法？比如，最小值什么
时候取得？
时候取得？
相关阅读
公司File了H1B transfer 2/16，大概什么时候能收到receiptInternship opening: Digital Beamforming现在uber内部的女生什么状态？Biostatistician opening我昨一个咳嗽吓坏几个种族歧视分子，令其惶恐几天太可怕了，两个白人被一个白人枪击说说我在pip期间被突然解雇当天的情况吧大家觉得cs 的这几个方向哪个现在状况最好，哪个未来发展最好六月份交的H1B还是pending 正常么？我同学在成都华为，刚给他打电话，结果他说。。。 (转载)susan之后，今天又一名uber女员工站出来揭批公司内幕 (转载)华为从15年就开始大规模裁减年老色衰的员工了，只不过做的比较(转载)装逼公司那么多人跑路，业界领先的hardcore的graph技术谁来做啊？我觉着华为裁员本质是买卖不行了 (转载)Uber的烙印SVP要走人了工程师职位电话面试看重的是什么才能进入On-site面试？Turn was acquiredRecruiter主动联系，但目前还没ready，该继续和Recruiter联系吗?任正非：华为没有退休金 大家如果不奋斗就垮了zt (转载)征正在刷题找工作的小伙伴