题外话：
好久没写博客了，主要觉得自己写的不怎么样，肚子没墨水了。今天又出来榨干肚子里的最后一滴墨水。
进入正题：
前面写过两篇动态规划的题目，今天又遇到动态规划了，想到了一个更容易理解的方法，我们用凑硬币这道题目来加深理解。网络上这个题目已经被写烂了，大多数文章都是复制粘贴的。本文原创。开始讲解之前读者需要了解递归。本文从递归解法讲起直到推出动态规划方法。
问题描述：
（凑硬币问题）给你 k 种面值的硬币，面值分别为 c1, c2 ... ck ，每种硬币的数量无限，
再给一个总金额 amount ，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回-1
这里我们k = 3 , c1 = 1、c2 = 3、c3 = 5.
1. 递归解法：
形象的理解递归：
比如f是一个八卦的人，有一天a和b谈恋爱了，只告诉了c。 f想知道a和b的关系， 就去问e， e说他自己不知道可以帮忙去问d，d说他也不知道可以帮忙去问c（递归调用过程），c呢就告诉了d，d又告诉了e，e告诉了f（回溯过程，回溯过程可以看作答案一步步传到f耳朵里的过程）。
用递归的思想来思考该问题大致如下：
我们知道amount=0和amount<0基本情况（c知道a和b的关系），求amount=11的答案（f想知道a和b的关系），ans(11)=ans（11-5）+1 or ans(11)= ans(11-3)+1 or ans(11)= ans(11-1)+1 （f去问了他认识的人e。如果f认识d或者直接认识c他可以更快的知道答案）。递归的回溯过程程序会自动完成。
def colCoins_rec(coins, amount):
"""
递归解法
:param coins: 硬币面值
:param amount: 总金额
:return: 凑齐总金额的最少硬币数量
"""
# 基本情况（c知道的情况）
if amount == 0:
return 0
if amount < 0:
return -1
res = float("inf")
# 有三种面值的硬币可以选择（f认识的人，因为f只认识e所以只有一个选择）
for coin in coins:
#选择（f选择问谁，交给谁来获取答案）
subproblem = colCoins_rec(coins, amount-coin)
# 子问题无解，（f问到了错误地人g，g是个孤儿谁都不认识，走到了死胡同，f要问下一个人）
if subproblem < 0: continue
# 选择最优的答案（如果f认识c，那么他很快可以获取答案，就可以选择这条信息链）
res = min(res, 1+colCoins_rec(coins, amount-coin))
return res
递归方法存在什么问题呢？很明显的一个是使用了函数调用栈，栈在计算机中是一个相对很有限的资源。还有一个是存在重叠子问题，导致了时间复杂度大大增加。LeetCode上这个方法一般是无法通过的。重叠子问题是什么呢？
h 存在直接连线的表示互相认识
/ \ 如果h想从c那里获得c知道的答案那么他要问认识的f，g同样
f g f，g要问他们认识的人。
/ \ / \ 观察发现f，e，g被问了多次！这是导致算法复杂度高的主要原因
g e e f
/ \ ........
e f
/ \
c d
如何解决上述存在的重叠子问题呢？答案是使用备忘录方法。
2备忘录递归方法
备忘录方法是这些人共用一个列表的，如果谁已经知道答案就填在列表对应的元素里里，每个人在问之前先访问列表，如果得到大难就不用再继续问下去了，避免重复的被问。
mem = [-1]*15
def colCoins_rec_mem(coins, amount, mem):
"""
在递归的解法的基础上加上备忘录解决重叠子问题。
:param coins: 硬币面值
:param amount: 总金额
:param mem: 备忘录
:return: 最少硬币数量
"""
# 基本情况（c知道的答案）
if amount < 0:
return -1
if amount == 0:
return 0
# 查看备忘录，看看是否计算过（是否被问过）
if mem[amount] != -1:
return mem[amount]
# 选择（询问的过程）
res = float("inf")
for coin in coins:
subproblem = colCoins_rec_mem(coins, amount-coin, mem)
if subproblem < 0: continue
res = min(res, 1+colCoins_rec_mem(coins, amount-coin, mem))
# 得到答案后写进备忘录
mem[amount] = res
return res
我们可以看到基于备忘录的递归算法，会在计算（询问）前去查看备忘录，避免重复计算。而且代码与纯递归方法也非常的相似。只多了查看备忘录的过程和获得答案后写进备忘录的操作。这个备忘录解决了重叠子问题，实际上他还是递归方法。我们可以看到其实备忘录记录的就是子问题和原问题的答案，递归方法是自顶向下的以“询问”的方法求得答案，那么可不可以让c主动的向他认识的人扩散答案直到让f知道答案。这个自底向上的“传播”就是动态规划！（好烦c这种人啊，就像我很烦动态规划题目）话不多说看代码
def colCoins_mem(coins, amount):
"""
自底向上递推出答案
:param coins: 硬币面值
:param amount: 总金额
:return:
"""
# 构造一个备忘录
mem = [0]*(amount+1) # mem[i]表示凑出金额i需要的最少硬币的数量
# 基本情况（这句代码可以不要）
mem[0] = 0
# 开始推导（c开始传播八卦了）
for i in range(1, amount+1):
# 从c开始向他认识的人传播消息
for coin in coins:
res = i - coin
if res >= 0:
mem[i] = mem[res] + 1
else:
continue
return mem[amount]
总结：
我们看看动态规划的要素就是：1、基本情况（知道答案的那个人）2、明确mem里面存储的是什么我们也可以称作状态。3、选择（每个状态有多少转移方方式）4、明确状态转移的细节（状态转移方程）。该文章一气呵成有什么不懂的留言，有空改一下。动态规划就到这里了。
