TOC
问题 假设你当前拥有 3 元 6 元 7 元的硬币 数量为无限。问 假设你需要组合出 18 元，如何使硬币的数量最少 分析：我认为这个问题有点类似于 01 背包问题，很明显是不能用贪心算法来解决的，因为贪心的去首选最大的硬币是无法做到最优的，所以需要一个回溯寻找最优的机制来帮助我们解决问题，很显然，动态规划是首选。让我们看看他是否能用动态规划解决。
- 最优子结构 假设需要组合 18 元，那么他其实完全可以基于一个比 18 小的数额 i 作为基础来进行硬币拼接，同时数额 i 仍然能够向下降低。所以他是拥有最优子结构的.
代码实现（python）
我们假设 d[i] 为当金额为 i 时，所需要的最小硬币数量，将 dg[i] 作为当金额为 i 时，所需要的最小硬币数量的组合方式。这是整个程序最核心的内容，并且将会保持不变，也就是循环不变式。在遍历硬币的过程中，去不断的尝试，能否找到使硬币的最小数量更小，直接的描述就是用于检测用一个 6 元的硬币能够抵消两个三元硬币，并且最小数量会降低，这就是回溯过程。举例:
但 i = 6 时 d[i - coin] + 1 等于 d[6 - 6] + 1 等于 d[0] 等于 1,这个 1 的意思就是 要凑六块钱，硬币数量最小为 1
def minNum(a, b):
return a if a < b else b
# i 当前计算的金额 从0开始 不断增长 结束于和目标金额相等
# num 目标金额
# coins 硬币规格数组
def minCoins(i, num, coins):
d = [0] * (num + 1)
dg = [[]] * (num + 1)
def _minCoins(i, num, coins):
if(i == 0):
d[i] = 0
_minCoins(1, num, coins)
return
min = 9999
for coin in coins:
if(i >= coin):
oMin = min
min = minNum(d[i - coin]+1, min) # 代码的核心，不断的回溯，去尝试硬币更少的组合方式
# 用于增加额外的信息 即组合方式
if(oMin != min):
copy = dg[i - coin][:]
copy.append(coin)
dg[i] = copy
d[i] = min
if(i == num):
return
else:
_minCoins(i+1, num, coins)
_minCoins(i, num, coins)
return d
# 硬币规格 无数量限制
coins = [3, 6, 7]
print(minCoins(0, 18, coins)[18])
最近在学python 感觉很有劲，简洁 语义化，不过字典没JS的对象字面量好用