找零钱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 楼
为什么所有的解法都只给出最小值，而不给出具体的怎么找的解法？比如，最小值什么
时候取得？
时候取得？
相关阅读
亚麻的MySQL组怎么样？能娶到聪明漂亮的白女绝对是祖坟冒青烟 (转载)开始layoff了，名单进行时yahoo开始layoff了,其他公司呢?刚面了walmart technology请教一个facebook的offer当烙印都不跟你说“Hi”的时候： 续集NJ有哪些IT公司?奇葩的店面国女面试真的很简单？微软某组招FTE Sr.Software Developer-C#, ASP.Net工作中不愿意求人，怎么样才能克服？ (转载)者明三姐到中国出任CTO (转载)哥大cs 16summer intern求推北京道路拥堵突然加剧 官方：网络约车是主因之一 (转载)烙印对学院院长的攻势 (转载)升职还是跳槽围棋下的好,是奴性的表现 (转载)感觉烙印人都不错，反而老美很烦人报包裹，顺便求比较 雅虎 和 甲骨文