1、动态规划原理：
适合应用动态规划求解的最优化问题应具备的两个要素：最优子结构和子问题重叠。

1.1、最优子结构： 如果一个问题的最优解包含其子问题的最优解，则该问题具有最优子结构。例子，长度为n的钢条的最优切割方案由第一次切割后两段钢条的最优切割方案组成；矩阵链问题同理。

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

• 原问题的最优解中涉及多少个子问题。例，钢条切割包含一个子问题；矩阵链问题两个。
• 在确定最优解使用那些子问题时，我们需要考察多少种选择。例，钢条切割要考虑n-1种切割位置。

1.2、子问题重叠： 问题的递归算法会反复求解相同的子问题。

2、矩阵链乘法问题解题步骤：

1、最优括号化方案的结构特征：
需要考察所有可能的划分点位置。

2、一个递归求解方案：

3、计算最优代价：
采用自底向上的表格法代替公式中的递归算法。

4、构造最优解：

参考资料： 算法导论，15.3 动态规划原理
总结：

1、通常最少需要两层循环，第一层为从小问题到大问题的遍历循环；第二层为寻找最优小问题解决方法（遍历以寻找最优分割点）。