注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为10分钟。
什么是动态规划？
上一节用中间结果的记录来解决递归算法的问题——极度低效，但这种方法还不能称为动态规划，而是叫作memorization（记忆化/函数值缓存），这种技术大大提高了递归解法的性能，甚至能降低递归解法的时间复杂度。
什么是动态规划解法？
动态规划算法采用了一种更有条理的方式来得到问题的解。
拿找零兑换的问题来说，动态规划算法从最简单的一分钱找零的最优解开始，逐步递加上去，直到我们需要的找零钱数。
在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零钱数，自然得到最优解。
在递加的过程当中，能保持最优解的关键是，其依赖于更少钱数最优解的简单计算，而更少钱数的最优解在前面的课程中已经得到了。这就是动态规划的解法。
问题的最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。
采用动态规划来解决11分钱的兑换问题
从1分钱兑换开始，一直到11分钱，逐步建立一个兑换表，如下图所示。
计算11分钱的兑换法，按硬币面值枚举：
- 减去1分硬币，剩下10分钱查表最优解是1。这种方法得到的结果是1+1=2个硬币。
- 减去5分硬币，剩下6分钱查表最优解是2。这种方法得到的结果是1+2=3个硬币。
- 减去10分硬币，剩下1分钱查表，最优解是1。这种方法得到的结果是1+1=2个硬币。
- 因为11分钱不足25分，所以减去25分面值的枚举不考虑在内。
通过上述最小值得到最优解：2个硬币。
按上面的思路，代码就不难写出来：
# 找零兑换：动态规划算法v1。
def dpMakeChange(coinValueList, change, minCoins):
# 从1分钱开始到change逐个计算最小硬币数。
for cents in range(1, change + 1):
# 1. 初始化一个最大值。
coinCount = cents
# 2. 减去每个硬币，向后查最少硬币数，同时记录总的最少数。
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
# 3. 得到当前最少硬币数，记录到列表中。
minCoins[cents] = coinCount
# 返回最后一个结果。
return minCoins[change] # 循环结束，得到最优解。
print(dpMakeChange([1, 5, 10, 21, 25], 63, [0] * 64))
<<<3
找零兑换问题动态规划算法的扩展
上面的动态规划算法代码中，函数dpMakeChange并不是递归函数。这是因为，这个问题是从递归算法开始的，但最终在尝试过程中，我们发现了一条更好更高效的算法，而这种算法并非递归算法。
动态规划中最主要的思想是：从最简单情况开始到达所需找零的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。
上面的找零兑换：动态规划算法v1已经得到了最小硬币的数量，但是没有返回硬币如何组合。扩展算法就是解决这个问题，其思路是在生成最优解列表的同时，跟踪记录所选择的那个硬币币值即可。
在得到最后的解之后，减去选择的硬币币值，回溯到表格之前的部分找零，就能逐步得到每一步所选择的硬币币值。
扩展后的动态规划算法的代码如下：
# 找零兑换：动态规划算法v2。
def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
# 从1分钱开始到change逐个计算最小硬币数。
for cents in range(1, change + 1):
# 1. 初始化一个最大值。
coinCount = cents
newCoin = 1 # 初始化一下新加的硬币。
# 2. 减去每个硬币，向后查最少硬币数，同时记录总的最少数。
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
newCoin = j # 对应最小数量，所减的硬币。
# 3. 得到当前最少硬币数，记录到列表中。
minCoins[cents] = coinCount
coinsUsed[cents] = newCoin
# 返回最后一个结果。
return minCoins[change] # 循环结束，得到最优解。
def printCoins(coinsUsed, change):
coin = change
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin
amnt = 63
clist = [1, 5, 10, 21, 25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print("Making change for", amnt, "requires")
print(dpMakeChange(clist, amnt, coinCount, coinsUsed), "coins")
print("They are:")
printCoins(coinsUsed, amnt)
print("The used list is as follows:")
print(coinsUsed)
<<<
Making change for 63 requires
3 coins
They are:
21
21
21
The used list is as follows:
[0, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]
<<<
To be continued.
