数据结构与算法

分治策略是解决问题的典型策略：分而治之。将问题分为若干更小规模的部分通过解决每一个小规模部分问题，并将结果汇总得到原问题的解。

递归算法体现了分治策略： 问题解决依赖于若干缩小了规模的问题，汇总得到原问题的解。

应用相当广泛： 排序、查找、遍历、求值等等，都用到了分治策略，且大多都是由递归算法实现的。

计算机科学中许多算法都是为了找到某些问题的最优解。我们很难计算出这些问题的最优解，只能不断的向这个最优解靠近。

一个经典案例是兑换最少个数的硬币问题：

假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币； 假设某次顾客投进1美元的纸币，买了37美分的东西，要找63美分，那么最少数量就是：两个25分硬币、一个10分硬币和三个1分硬币，一共6个硬币。

解决上面的找零问题，我们的第一反应通常是使用最直观的“贪心策略”。使用如下方法解决：

从面值最大的硬币开始，尽量找大面值的硬币，等剩余要找的钱不足一个该面值的硬币，再换面值小一点的找零，以此类推。

还是找零问题，但这次硬币的面值除了上面的三种外，多了一种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次，例如美元硬币体系：

从上述4项中选择最小的一个。

python代码实现：