文章目录
- 一、分治策略与递归算法
-
- 1. 分治策略的概念
- 2. 分治策略与递归算法的关系
- 二、优化问题和贪心策略
-
- 1. 优化问题
- 2. 贪心策略
- 3. 贪心策略失效
- 三、找零问题的递归解法
-
- 改进递归算法解决方案
- 四、找零问题的动态规划解法
-
- 1. 动态规划解法
- 2. 动态规划中最主要的思想
- 3. 找零兑换：动态规划算法扩展
一、分治策略与递归算法
1. 分治策略的概念
分治策略是解决问题的典型策略：分而治之。将问题分为若干更小规模的部分通过解决每一个小规模部分问题，并将结果汇总得到原问题的解。
2. 分治策略与递归算法的关系
-
递归算法体现了分治策略：
问题解决依赖于若干缩小了规模的问题，汇总得到原问题的解。
-
应用相当广泛：
排序、查找、遍历、求值等等，都用到了分治策略，且大多都是由递归算法实现的。
二、优化问题和贪心策略
1. 优化问题
计算机科学中许多算法都是为了找到某些问题的最优解。我们很难计算出这些问题的最优解，只能不断的向这个最优解靠近。
一个经典案例是兑换最少个数的硬币问题：
假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币；
假设某次顾客投进1美元的纸币，买了37美分的东西，要找63美分，那么最少数量就是：两个25分硬币、一个10分硬币和三个1分硬币，一共6个硬币。
2. 贪心策略
解决上面的找零问题，我们的第一反应通常是使用最直观的“贪心策略”。使用如下方法解决：
从面值最大的硬币开始，尽量找大面值的硬币，等剩余要找的钱不足一个该面值的硬币，再换面值小一点的找零，以此类推。
3. 贪心策略失效
还是找零问题，但这次硬币的面值除了上面的三种外，多了一种21美分的面值。
此时，如果还按照贪心策略，则需要 25 × 2 + 10 × 1 + 1 × 3 25 \times 2 + 10 \times 1 + 1 \times 3 25×2+10×1+1×3，总共六个硬币。因为，找完两个25美分后，剩下的13美分不足一个21美分硬币。所以，没有使用21美分硬币。
但如果一上来就使用21美分硬币，那么则只需要三个21美分硬币。
贪心策略最终失效了，没有给出最优解。
三、找零问题的递归解法
接下来的递归算法则弥补了贪心算法的不足，它可以百分之百的给出最优解。
-
首先是确定基本结束条件，兑换硬币这个问题最简单直接的情况就是，需要兑换的找零，其面值正好等于某种硬币。
如找零25分，答案就是1个硬币！
- 其次是减小问题的规模，我们要对每种硬币尝试1次，例如美元硬币体系：
-
找零减去1分后，求兑换硬币最少数量（递归调用
自身）；
-
找零减去5分后，求兑换硬币最少数量（递归调用
自身）；
-
找零减去10分后，求兑换硬币最少数量（递归调用
自身）；
- 找零减去25分(quarter)后，求兑换硬币最少数量（递归调用自身）；
-
python代码实现：
def recMC(coinValueList, change):
"""
使用递归算法解决找零问题
:param coinValueList: 货币体系，是一个列表，保存硬币的各种面值
:param change: 找零的金额
:returns: 找零花费的最少硬币数量
"""
# 初始化最少硬币数
minCoins = change
# 递归出口：如果要找的金额恰好是某一个面值的硬币就返回1
if change in coinValueList:
return 1
# 否则，从货币体系中选取一个面额，并且面额要比找零金额要小
else:
for i in [c for c in coinValueList if c <= change]:
# 从找零钱数中减去面额的金额，传入递归调用
numCoins = 1 + recMC(coinValueList, change - i)
# 每次循环都去对比花费硬币的数量，寻找最少的数量
if numCoins < minCoins:
minCoins = numCoins
return minCoins
# 测试用例
print(recMC([1, 5, 10, 25], 63))
这段代码有点难懂，但其实它的实质是排列组合出所有的找零可能，因此，它的效率极其的低！
我在电脑上运行上述测试用例，花费了近20秒。然后加了一种面额，并提高找零金额到93，等了3分钟还没出结果，就放弃了😕
以找零26分钱为例，画出部分调用过程（377次递归的一小部分）：
从图中可以发现，递归算法的重复计算太多，比如找零15分出现了3次，而这仅仅是一小部分。
所以，对这个递归解法进行改进的关键就在于消除重复计算。
改进递归算法解决方案
我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过。
在递归调用之前，先查找表中是否已有部分找零的最优解。如果有，直接返回最优解而不进行递归调用；如果没有，才进行递归调用。
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
print(recDC([1,5,10,25],63,[0]*64))
对于63分钱的找零问题，改进后的算法仅仅需要211次递归调用，是改进之前的三十万分之一，瞬间返回！
四、找零问题的动态规划解法
上面改进后的算法，将中间结果记录了下来，可以很好的解决找零兑换问题。但这种方法还不能称为动态规划，而是叫做“memoization（记忆化/函数值缓存）”。
1. 动态规划解法
依旧是以找零问题为例：动态规划算法从最简单的“1分钱找零”的最优解开始，记录下最优解，逐步递加上去（2分钱的最优解，3分钱的……），直到我们需要的找零钱数。
计算11分钱的兑换法，我们做如下几步，从1分钱兑换开始，逐步建立一个兑换表（横向代表找零金额，纵向为需要的最少硬币数）：
- 首先减去1分硬币，剩下10分钱查表最优解是1
- 然后减去5分硬币，剩下6分钱查表最优解是2
- 最后减去10分硬币，剩下1分钱查表最优解是1
通过上述最小值得到最优解：2个硬币
问题的最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。在找零问题中，这句话的意思就是找5分钱的最优解，我们必须拥有4分钱的最优解。
python代码实现：
def dpMakeChange(coinValueList,change,minCoins): # minCoins用来存储上面的那张表，大小为找零金额加一
# 从1分钱开始到change，因为range是左闭右开区间，所以加1
for cents in range(change+1):
# 初始化硬币数量，放入最大值
coinCount = cents
# 从cents中减去一种面值的金额
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
# 得到当前的最优解
minCoins[cents] = coinCount
# 返回整体的最优解
return minCoins[change]
def dpMakeChange(coinValueList, change, minCoins):
# 从1分钱开始到change，因为range是左闭右开区间，所以加1
for cents in range(change + 1):
# 初始化硬币数量，放入最大值
coinCount = cents
#
for j in [c for c in coinValueList if c <= cents]:
# 从cents中减去所选面值的金额，剩余金额的最优解查表获取
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
# 得到当前的最优解
minCoins[cents] = coinCount
# 返回整体的最优解
return minCoins[change]
print(dpMakeChange([1, 5, 10, 21, 25], 63, [0]*64))
# 输出：3
注意：这不是一个递归算法！
2. 动态规划中最主要的思想
从最简单情况开始到达所需找零的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。
3. 找零兑换：动态规划算法扩展
前面的算法已经得到了最少硬币的数量，但没有返回硬币如何组合。我们现在想要具体的硬币组合，就需要对算法进行拓展。
扩展算法的思路很简单，只需要在生成最优解列表同时跟踪记录所选择的那个硬币币值即可。
而在得到最后的解后，查询一下对应金额记录的步骤，然后减去选择的硬币面额，再到记录中查询那一次所使用的面额……。如此反复回溯到表格之前的部分找零，就能逐步得到每一步所选择的硬币币值。
python代码实现：
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(coinsUsed, change):
coin = change
while coin > 0:
# 到面额记录中查询记录
thisCoin = coinsUsed[coin]
print(thisCoin)
# 减去面额后再次查询
coin = coin - thisCoin
def main():
amnt = 63
clist = [1, 5, 10, 21, 25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print("找零", amnt, "分钱需要：")
print(dpMakeChange(clist, amnt, coinCount, coinsUsed), "个硬币")
print("它们是：")
printCoins(coinsUsed, amnt)
print("面额记录如下：")
print(coinsUsed)
main()
"""
输出：
找零63分钱需要：
3 个硬币
它们是：
21
21
21
面额如下：
[1, 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]
"""
注意看面额21的位置：恰好就是63，63-21，63-21-21，这三个位置。