dynamic programming通过组合子问题的解来求解原问题。
动态规划适用于子问题重叠的情况，即不同的子问题拥有公共的子子问题。动态规划对每个子子问题只求解一次，将其保存在一个表格中，从而无需每次求解一个子子问题时都需要重新计算。
动态规划常用来求解最优化问题（optimization problem）。这类问题可以有很多可行的解，每个解都有一个值，我们希望寻找最优值，这称为问题的一个最优解(an optical solution)而不是最优解(the optical solution)。
我们通常按如下4个步骤设计一个动态规划算法：

1. 刻画一个最优解的结构特征
2. 递归的定义最优解的值
3. 计算最优解的值，通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

动态规划算法的底层是递归，递归本质上是没有性能问题的，之所以出现问题是因为重复递归导致的，带有记忆的递归可以避免重复递归的问题。

1. 钢条切割

购买长钢条，将它切割为短钢条出售，切割工序没有成本。假定出售一段长度为i英寸的钢条的价格为p_i，i=1，2，...，n
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表p_i。求切割钢条方案，使得销售收益r_n最大。注意，如果长度为n英寸的钢条的价格p_n足够大，最优解可能就是完全不需要切割。
长度为n英寸的钢条共有2^n-1种不同的切割方案，因为在距离钢条左端i英寸处，我们总是可以选择切割或者不切割。如果一个最优解将钢条切割为k段（1 <= k <= n），那么最优切割方案为：
n = i₁ + i₂ + ...+ i_k
将钢条切割为 i₁，i₂，i_k的小段，得到最大收益：
r_n = p_i1 + p_i2 +...+ p_ik

价格表

切割方案

image.png

自顶向下递归实现

问题工作量与问题规模成指数关系

使用动态规划方法求解最优钢条切割问题
将CUT-ROD转换为一个更高效的动态规划算法：朴素的递归调用之所以效率很低，是因为反复求解相同的子问题，动态规划方法仔细安排求解顺序，对每一个子问题只求解一次，并将结果保存下来，如果需要再次计算这个子问题，只需要查找保存的结果，不必重新计算，因此动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡（以空间换时间）的例子。时间的节省可能是非常大的：将指数时间转化为一个多项式时间。如果子问题数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子问题，那么动态规划方法的总运行时间就是多项式阶的。
动态规划有两种等价的实现方法：
①带备忘录的自顶向下法（top-down with memoization)，仍然是递归，但是在过程中会保存每个子问题的解。当需要一个子问题的解时，过程首先检查是否保存过这个解。
②自底向上法（bottom-up method），任何子问题的求解只依赖于更小的子问题的求解，因此我们可以将子问题按照规模排序，按由小到大的顺序进行求解。当求解某个子问题时，它所依赖的更小的子问题已经求解完毕，结果都已经保存。每个子问题只需要求解一次，当我们求解到它时，所有的前提子问题都已经求解完成！

两种算法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向下法的时间复杂度系数可能更小！

带备忘录的自顶向下法

自底向上法

重构解
前面的几种办法给出钢条切割问题的动态规划算法返回最优解的收益值，但未返回解本身（一个长度列表，给出切割后每段钢条的长度）。我们可以扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案，利用这些方案，我们就能输出最优解。

重构解

image.png

动态规划原理

应用动态规划方法求解最优化问题应该具备两个要素：最优化结构和子问题重叠。
如何借助备忘机制来充分利用子问题重叠特性？

最优子结构

如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。动态规划使用子问题最优解来构造原问题最优解，因此，我们需要确保考察了最优解中用到的所有子问题。
在发掘最优子结构性质的过程中，实际上遵循了如下的通用模式：

1. 证明问题最优解的第一个组成部分是做出一个选择，例如，选择钢条第一次切割位置，选择矩阵链的划分位置等。作出这一选择会产生一个或者多个待解的子问题。
2. 对于一个给定问题，在其可能的第一部选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何刻画子问题空间
4. 利用剪切-粘贴技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

一个刻画子问题空间的好经验是：保持子问题空间尽可能简单，只在必要时才扩展它。例如，我们在求解钢条切割问题时，子问题空间中包含的问题为：对每个i值，长度为i的钢条的最优切割问题。这个子问题空间很有效，因此我们不必尝试更一般性（从而也更大）的子问题空间。

对于不同问题领域，最优子结构的不同体现在两个方面：

1. 原问题的最优解中涉及多少个子问题
2. 在确定最优解使用哪些子问题时，我们需要考察多少种选择。
   在钢条切割问题中，长度为n的钢条的最优切割方案仅仅使用一个子问题（长度为n-i的钢条的最优切割），但我们必须考察i的n种不同取值，来确定哪一个会产生最优解。A_iA_i+1...A_j的矩阵链乘法问题中，最优解使用两个子问题，我们需要考察 j-i 种情况。对于给定的矩阵链划分位置——矩阵A_k，我们需要求解两个子问题——A_iA_i+1...A_k和A_k+1A_k+2...A_j的括号化方案，两个子问题都必须求解最优方案。一旦我们确定了子问题最优解，就可以在 j-i 个候选的k中选取最优者。
   我们可以用子问题的总数和每个子问题需要考察多少种选择这两个因素的乘积来粗略分析动态规划算法的运行时间。对于钢条切割问题，共有O(n)个子问题，每个子问题最多需要考察n种选择，因此运行时间为O(n²)。矩阵链乘法问题共有O(n²)个子问题，每个子问题最多需要考察n-1种选择，因此运行时间为O(n³)。
   在动态规划算法中，我们通常自底向上的使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价再加上由此次选择直接产生的代价。例如，对于钢条切割问题，我们首先求解子问题，确定长度为i = 0，1，...，n -1的钢条的最优切割方案，然后利用公式
   
   公式
   
   确定哪个子问题的解构成长度为n的钢条的最优切割方案，此次选择本身所产生的代价就是p_i。
   贪心算法与动态规划很相似，他也必须具有最优子结构性质。不同之处在于，他并不是寻找子问题最优解，然后在其中选择，而是首先做一次“贪心”选择——在当时看来最优的选择——然后求解选出的子问题，从而不必费心求解所有可能相关的子问题。在某些情况下，这一策略也能得到最优解！

重叠子问题

适合用动态规划算法求解的最优化问题应该具备第二个性质：子问题空间必须足够小，即问题的递归算法会反复的求解相同的子问题，而不是一直生成新的子问题。一般来讲，不同子问题的总数是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。
与之相对的，适合用分治方法求解的问题通常在递归的每一步产生一个全新的子问题。动态规划算法通常这样利用重叠子问题性质：对每个子问题求解一次，将解存入一个表中，当再次需要这个子问题时直接查表，每次查表的代价为常量时间。

重构最优解

我们将每个子问题所做的选择存放在一个表中，这样就不必根据代价值来重构这些信息。
备忘
带备忘录的递归算法为每个子问题维护一个表项来保存他的解。每个表项的初值设置为一个特殊值，表示尚未填入子问题的解。当递归调用过程中第一次遇到子问题时，计算其解，并存入对应表项。随后每次遇到同一子问题，只是简单的查表，返回其解。
通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快(都是O(n³)时间，相差一个常量系数)， 因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且，对于某些问题，我们可以利用表的访问模式来进一步降低时空代价。相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。