|
|
|
|
|
|
i****y 发帖数: 84 | 1 请问找零钱最少的问题,如果找不出怎么办,比如没有1cent只有2cent的面值,一般这
样的问题该怎么处理呢?
opt[3] =opt[3-2]+1;
可是没1cent然后咋办?设opt[1] = max_value? | k**********y 发帖数: 20 | 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?
| s****p 发帖数: 124 | 3 为什么所有的解法都只给出最小值,而不给出具体的怎么找的解法?比如,最小值什么
时候取得? |
|
|
|
|
|
|