动态规划通常用于求解最优化问题
与分治方法不同，动态规划应用于子问题重叠的情况，通过保存中间解，避免重复计算同样的子问题
设计动态规划算法的步骤：
1.刻画一个最优解的结构特征
2.递归地定义最优解的值
3.计算最优解的值，通常采用自底向上的方法
4.利用计算出的信息构造一个最优解
钢条切割
给定钢条长度 n 和不同长度钢条的价格表，计算切割钢条的最大价值
核心思路：
1.将钢条分为两段，左段长度为 i，右段长度为 n-i，钢条的价值为左右段的价值之和
2.左段的价值从价格表中获取，右段的价值递归切割求解
3.求最优解需要在一次切割中对 i 遍历计算，取最优值
上述算法的性能非常差，为 O(2的n次方)，使用动态规划保存子问题的解，可以将性能提高到 O(n的平方)
有两种具体的实现方法：
1.带备忘的自顶向下法
2.自底向上法
子问题图
也可以用子问题图来分析动态规划算法的性能：将问题转化为子问题图后，动态规划的运行时间与图中顶点和边的数量呈线性关系
重构解
如果还需要最优解的切割方案，则需要维护额外的信息
书中使用的方法让感觉有点惊艳，只需要保存子问题的第一段钢条的最优切割长度 s 到一个数组中，然后通过一个 O(n) 的操作即可输出切割方案
矩阵链乘法
矩阵链乘法问题可描述为：对给定的 n 个矩阵的链，求完全括号化方案，使得计算乘积所需的标量乘法次数最少。
自底向上的表格法，和算法图解里面的动态规划用的表格法是一类的，这个表格法才是动态规划方法名字的来源，规划指的就是表格。通过表格记录子问题的解，自底向上的迭代，新问题的解可以由已计算完毕的子问题的解得出，不需要重新计算。
再次感叹算法的精妙，解决矩阵链乘法这样复杂的问题，只需要十几行伪代码，核心代码不超过十行，已经无法直视 Objective-C 的臃肿了。
动态规划方法解决此问题的性能为 O(n的三次方)，比暴力穷举方法的 O(2的n次方) 要高效很多。
动态规划原理
适合用动态规划解决的最优化问题应该具备两个要素：
1.最优子结构
2.子问题重叠
如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质
在确定解决问题的方案时，我们需要考虑：
1.原问题的最优解中涉及多少个子问题
2.在确定最优解使用哪些子问题时，我们需要考察多少种选择
可以通过这两点的选择粗略分析动态规划算法的运行时间
在分析一个问题是否具有最优子结构性质时，我们需要仔细分析，其中需要注意的一点是分解后的子问题是否是无关的
无权最短路径问题，无权最长路径问题
如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质
对重叠子问题只计算一次，其它时候直接利用存储的结果是动态规划算法高性能的关键
重构最优解
如果需要输出最优化问题的方案，则需要将每个子问题所做的选择存储下来，在动态规划运行完毕后，输出最优解的方案只需耗费极少的时间
带备忘的自顶向下方法（递归方法）可以和自底向上方法达到同样的效率，我感觉用递归的方法分析问题思考起来会比较简单，写代码也比较清晰，但是需要增加额外的递归调用开销（会使性能的常量系数有差距）。假如某些子问题不必求解，备忘方法会提现出优势。
最长公共子序列
最长公共子序列问题的现实意义是，可以用来比较两个序列的相似性。
最长公共子序列：LCS
最优子结构：两个序列的 LCS 包含两个序列的前缀的 LCS
思路的关键是公式 15.9（来自定理 15.1）：当 x[i] = y[j] 时，子问题为 X[i-1] 与 Y[j-1] 的 LCS，否则应求解两个子问题：X[i-1] 与 Y[j] 的 LCS、X[i] 与 Y[j-1] 的 LCS
使用自底向上的方法计算，可以在 O(mn) 时间内解决
最优二叉搜索树
假设二叉搜索树的每个结点（包括叶子结点）都有已知被搜索到的概率，最优二叉搜索树就是搜索操作查询结点数期望最小的树。
暴力枚举解决这个问题需要指数级的时间。
最优子结构：最优二叉搜索树的子树也必然是子树元素集合的最优解
看这一段证明的时候产生了一个疑问，会不会有一个子树不是最优解，但是和另一颗子树组合的情况是整体的最优解呢？并不会，树的根结点选定后，两个子树就只能在固定的元素集中生成子树，这是二叉搜索树的性质导致的。
e[i,j] 为第i到j个元素组成的最优二叉搜索树的搜索期望。
子问题是重叠的
可以在 O(n的平方) 时间内解决问题
网友评论