|
|---|
|
|
|
|
|
|
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 为什么所有的解法都只给出最小值，而不给出具体的怎么找的解法？比如，最小值什么
时候取得？ |
|
|
|
|
|
|
|
