动态规划
在前面的小节中我们了解了递归的基本思想，我们可以把复杂问题转换成极小的问题从而把复杂的问题简单化，我们可以对递归思想进一步的改造，当我们转换的小问题能够重复使用（调用）的时候，产生了一个新的思想——动态规划（Dynamic Programming）。
举个例子
举个在生活中非常常见的例子来讲解一下动态规划：在纸币广泛流行的时代，我们使用纸币购物的时候总是会涉及到找零的问题，假设我们身上有足够的1、5、10、20、50元面值的纸币，我们的目标就是对于给定的找零数值n，使得我们使用到尽量少的钞票（张数少）。
根据花钱的经验，看到这个问题，我们肯定会想到这样的策略：1、尽可能多的使用面值最大的纸币，2、尽可能使用面值第二大的......以此类推。根据此类策略，我们是可以使用该方法去实现我们使用到最少钞票的目的的，这种方法我们也称之为贪婪算法。比如：63 = 50+10+1*3。
现在走一个不常规的路线（毕竟编程场景和生活有所不同），某个国家的纸币面额有1、5、11三种，现在我们想要找零的钱数是15元，会得到如下的结果：
- 贪婪算法：15 = 11+1*4（5张）
- 正确答案：15 = 5*3（3张）
这种情况下我们会发现，我们之前使用的贪婪算法出错了，贪婪算法让我们只考虑了眼前情况下的利益，并没有去考虑整体，自然就会产生错误了。
多个角度思考这个问题（用f(n)中的n表示金额）：
先选11元会是什么情况？
- 需要张数 = f(4) +1 = (1元)*4 + 1 = 5张
- 上面的1表示用掉一张11元纸币，下同。
先选5元会是什么情况？
- 需要张数 = f(10) + 1 = (5元)*2 + 1 = 3张
先选1元会是什么情况？
- 需要张数 = f(14) + 1 = (11元)*1 + (1元)*3 + 1 = 5张
根据上述过程通过尝试把所有类型的纸币都先做选取，可以找到正确的决策，因此可以得到上述方法的核心：
我们对于找零数值n和最小纸币的张数f(n)有结论：f(n)只与f(n-11)，f(n-5)，f(n-1)相关，因此可以得到我们计算的方法就是：
有了这个关于f(n)式子，我们是不是就可以求得任何f(n)的值了呢？同样我们也可以递归的调用f(n)的表达式，这就是我们实现动态规划的思想。（后续会通过代码实现）
动态规划三步走
- 建立状态转移方程
这一步是我们进行动态规划的核心，其核心就在于：当我们已经知道$f(1)-f(n-1)$的值，然后我们需要想办法用它们求得$f(n)$，得到一个状态转移方程（公式）。
- 缓存并复用以往结果
这一步主要是为了加快我们的运算过程，简单的说如果现在$f(100)$未知，但是我们刚刚求得$f(99)$，如果不将$f(99)$缓存起来，那么我们再求$f(100)$的时候就又要求一遍前面所有项的和，这也就体现出了我们需要进行缓存复用的重要性。
- 按顺序从小往大算
在寻找和使用状态转移方程的时候，我们基本都是通过前几项：$f(0),f(1),f(2),f(3)$来找到其中的转移状态，所以通常情况下我们只能从小往大一点点的进行计算，否则可能会打乱自己的思路。
递归实现代码（示例）
使用最简单的递归的方法我们可以得到上述问题的求解，但是递归的时候我们近乎于列举出了所有情况，然后再去寻找所用纸币张数最少的那个方案，先来看一下递归的实现方法：
# dp动态规划
'''
参数说明：
coinValueList:已有的硬币种类（list）
change:需要凑出的钱数
knownResults:全0的列表，用于存储前面计算过的结果
'''
def recDC(coinValueList, change, knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
# 遍历选取每一种硬币
for i in [c for c in coinValueList if c <= change]:
# 抛除已选择硬币，对剩下的钱递归处理
numCoins = 1 + recDC(coinValueList, change - i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins
recDC([1, 5, 11], 63, [0] * 64)
# 输出
# 9动态规划（示例）
使用动态规划我们能够避免像递归一样繁琐的列举过程，根据上面提到过的动态规划三步走，我们从1元钱的找零开始，然后是2元、3元，这其实就是我们在计算f(0)、f(1)、f(2)的过程，这样计算下去，当我们找零金额为n元的时候，我们不仅可以计算出f(n)，还可以得到f(n-1)、f(n-2)...f(0)这些结果，此时如果我们的找零金额比n小，那么我们就可以直接得到结果了。动态规划具体的代码实现如下：
# dp动态规划
def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
for cents in range(change + 1):
coinCount = cents
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
# 动态转移找最小
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
newCoin = j
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
return minCoins[change]
def printCoins(coinValueList, change, minCoins, coinsUsed):
minc = dpMakeChange(coinValueList, change, minCoins, coinsUsed)
print("最小纸币数：", minc)
coin = change
print("所需纸币面额：")
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin
c1 = [1, 5, 11]
coinsUsed = [0] * 64
coinCount = [0] * 64
printCoins(c1, 17, coinCount, coinsUsed)
# 输出
'''
最小纸币数： 3
所需纸币面额：
1
5
11
1
'''