找零兑换的优化问题的三种解决方法

    计算机科学中很多算法都是为了找到某些问题的最优解，这就是优化问题。

    例如下图，找到两个点之间的最短路径，这就是优化问题

地图

    而优化问题的经典案例就是兑换最少个数的硬币问题。比如顾客购物买37元东西，给了100元，要找63元，那最少数量就是1张50元，1张10元，1张2元1张1元，一共4张。

方法1:贪心策略

 解决这个问题，最直观的就是使用贪心策略。我们会从最大面值的钱开始，用最多的数量。有余额再到下一个最大面值，还用最多的数量，一直到1元为止。

    贪心策略在人民币的体系下表现还好，但是如果当存在有21元的面值，贪心策略就会失效。因为63元的最优解是3个面值21元。

方法2:递归解法

     既然贪心策略在特殊的面值下会失效，那我们用递归解决这个问题吧。

    递归的三个首先条件，我们先确定基本结束条件：剩余需要兑换的零钱正好等于某面值。例如找零10元，答案就是1张10元。

    其次是缩小问题的规模，例如美元硬币体系，如下图：

缩小问题的规模

    4种面值则都试用递归调用自身，但选择数量最小的一个。

    递归解法代码如下：

递归解法代码

    上面递归解法虽然能解决问题，但最大的问题是：非常低效！例如对63元的兑换问题需要进行6千多万的递归调用，有太多的重复计算。所以优化这个算法，我们需要消除重复的计算。

    我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过。这个算法的中间结果就是部分找零的最优解，在递归调用之前先查找表中是否已有部分找零的最优解，如果有，直接返回最优解而不进行递归调用，如果没有，才进行递归调用。

        改进代码如下：

递归解法改进代码

    改进后的解法，极大的减少了递归调用次数。对63元的兑换问题仅需要进行221次的递归调用，是改进前的三十万分之一。这种中间结果记录的方法叫做“memoization”（记忆化/函数值缓冲）技术，提高了递归解法的性能，这种方法的应用如缓冲。

方法3:动态规划解法

    动态规划（Dynamic programming，简称DP）主要用来解决一些希望找到问题最优解的优化问题。

    找零兑换的动态规划算法从最简单的“1元钱找零”的最优解开始，逐步递加上去，直到我们需要的找零数。在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零数，自然得到最优解。

    递加的过程能保持最优解的关键是，其依赖于更少钱数最优解的计算，而更少钱数的最优解已经得到了。问题的最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。

    我们举个例子，采用动态规划来解决11分钱的兑换问题，从1分钱兑换开始，逐步建立一个兑换表。（美元硬币包含1、5、10、25四种）

兑换表

    计算11分钱的兑换法，我们做如下几步：

1、减去1分钱，剩下10分钱查表最优解是1

2、然后减去5分钱，剩下6分钱查表最优解是2

3、最后减去10分钱，剩下1分钱查表最优解是1

通过上述最小值得到最优解：2个硬币

    找零兑换：动态规划算法代码如下，有三个入参：

动态规划算法代码

    我们注意到动态规划算法dpMakeChange并不是递归算法，且该算法没有返回硬币是如何组合的，所以想要得到硬币的组合需要扩展算法，在生成最优列表同时跟踪记录所选择的那个币值。在得到最优解后，减去选择的硬币币值，回溯到表格之前的部分找零，就能逐步得到每一步得到的币值。

    扩展算法代码如下：

扩展算法代码

    我们都知道动态规划算法有两种形式：①自顶向下的备忘录法 ②自底向上。

    其中零钱兑换的解法2就是自顶向下的备忘录法，避免重复执行。而解法3是自底向上动态规划，先计算子问题，再由子问题计算父问题。