动态规划来解决一些最优解的问题，常常可以将暴力算法的指数级时间复杂度降到O(n2)和O(n3)。动态规划并不难，只要按四个步骤就能找出最优解。 刻画一个最优解的结构特征。 递归地定义最优解的值。 计算最优解的值，通常使用自底向上的方法。 利用计算出的信息构造一个最优解。 动态规划的两个要素：最优子结构和子问题重叠。 最优子结构：如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。 子问题重叠：递归算法反复求解相同的子问题， ...