你好，我是卢誉声。今天我们来继续学习动态规划。

在前面的几节课中，我们经历了贪心算法求解硬币找零的问题，并从中发现了贪心算法本身的局限性：它几乎只考虑了局部最优，因此无法应对需要考虑整体最优的算法面试问题。

针对这一问题，我们重新思考了解决方案，用递归的方法来 穷举 出所有可能的组合，从这些可能组合中找出最优解。虽然这么做考虑了整体最优，而且真的可以解决问题，但效率太低。因此，为了解决这个低效问题，我们又提出了备忘录的概念，并在硬币找零案例中应用它解决了问题。

你应该发现了，我们在解决硬币找零问题时的思路是一以贯之的：发现问题，找解决方案；如果方案有局限性，那么就看如何扩展视野，找寻更优的方法。

不知道你还记不记得，我在上一节课的结尾有提到：含有备忘录的递归算法已经与动态规划思想十分相似了，从效率上说也是如此。

事实上，你已经在使用动态规划的思想解决问题了。但 “真正”的动态规划解法跟备忘录法又有什么区别呢？

接下来我们就带着这个问题，一起来学习今天的内容吧！

我们曾不止一次提到重叠子问题，并在上一课对其做了深入探讨。其实，重叠子问题是考虑一个问题是否为动态规划问题的先决条件，除此之外，我还提到了无后效性。

嗯，是时候对这些问题做个总结了，动态规划问题一定具备以下三个特征：

这是我第一次在课程中提出 最优子结构 这一概念，所以咱们先了解一下。这东西乍一听有些玄乎，什么叫子问题之间必须相互独立？我举一个简单的例子，你就明白了。

比如说，假设你在外卖平台购买5斤苹果和3斤香蕉。由于促销的缘故，这两种水果都有一个互相独立的促销价。如果原问题是让你以最低的价格购买这些水果，你该怎么买？显然，由于这两种水果的促销价格相互独立、互不影响，你只需直接购买就能享受到最低折扣的价格。

现在我们得到了正确的结果：最低价格就是直接购买这两种折扣水果。因为这个过程符合最优子结构，打折的苹果和香蕉这两个子问题是互相独立、互不干扰的。

但是，如果平台追加一个条件：折扣不能同时享用。即购买了折扣的苹果就不能享受折扣的香蕉，反之亦然。这样的话，你肯定就不能同时以最低的苹果价格和最低的香蕉价格享受到最低折扣了。

按刚才那个思路就会得到错误的结果。因为子问题并不独立，苹果和香蕉的折扣价格无法同时达到最优，这时最优子结构被破坏。

回过头来，我们再读一下最优子结构的定义。首先，你应该已经理解了什么是子问题之间必须相互独立。

其次，所谓后续的计算可以通过前面的状态推导，是指：如果你准备购买了5斤折扣苹果，那么这个价格（即子问题）就被确定了，继续在购物车追加3斤折扣香蕉的订单，只需要在刚才的价格上追加折扣香蕉的价格，就是最低的总价格（即答案）。

现在，让我们回到硬币找零的问题上来，它满足最优子结构吗？满足。

假设有两种面值的硬币 c[0]=5, c[1]=3，目标兑换金额为 k=11。原问题是求这种情况下求最少兑换的硬币数。

如果你知道凑出 k=6 最少硬币数为 “2”（注意，这是一个子问题），那么你只需要再加 “1” 枚面值为 c[0]=5 的硬币就可以得到原问题的答案，即 2 + 1 = 3。

原问题并没有限定硬币数量，你应该可以看出这些子问题之间没有互相制约的情况，它们之间是互相独立的。因此，硬币找零问题满足最优子结构，可以使用动态规划思想来进行求解。

当动态规划最终落到实处，就是一个状态转移方程，这同样是一个吓唬人的名词。不过没关系，其实我们已经具备了写出这个方程的所有工具。现在，就让我带你一起看看如何写出这个状态转移方程。

首先，任何穷举算法（包括递归在内）都需要一个终止条件。那么对于硬币找零问题来说，终止条件是什么呢？当剩余的金额为 0 时结束穷举，因为这时不需要任何硬币就已经凑出目标金额了。在动态规划中，我们将其称之为 初始化状态。

接着，我们按照上面提到的凑硬币的思路，找出子问题与原问题之间会发生变化的变量。原问题指定了硬币的面值，同时没有限定硬币的数量，因此它们俩无法作为“变量”。唯独剩余需要兑换的金额是变化的，因此在这个题目中，唯一的变量是目标兑换金额 k。

在动态规划中，我们将其称之为 状态参数。同时，你应该注意到了，这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。

接着，既然我们确定了状态，那么什么操作会改变状态，并让它不断逼近初始化状态呢？每当我们挑一枚硬币，用来凑零钱，就会改变状态。在动态规划中，我们将其称之为 决策。

终于，我们构造了一个初始化状态->确定状态参数->设计决策的思路。现在万事俱备，只欠东风，让我们一起来写这个 状态转移方程。通常情况下，状态转移方程的参数就是状态转移过程中的变量，即状态参数。而函数的返回值就是答案，在这里是最少兑换的硬币数。

我在这里先用递归形式（伪代码形式）描述一下状态转移的过程，这跟我们在上面讨论的挑硬币的过程是一致的。

顺着这个思路，我把状态转移方程给写出来，它是这样的：