用动态规划求解问题 和分治法是类似的。

首先要减少问题的规模。

分治法的问题：自顶向下会对子问题进行重复计算,时间复杂度会达到指数级.

但是动态规划是从自底向上，为了避免重复计算，采用查表(数组)的方式。

矩阵链乘的最优子结构的性质的表现形式和装配线调度是不一样的，要复杂一些。

1-n有n-1种。

最优子结构：问题分解后所有子问题的解都是最优的

上面就是递归式

底是什么？

实际上在实际应用当中，不管问题怎样复杂，本质上来讲，基本上和装配线调度问题和矩阵链乘问题是一样的。

如果能对上面2个问题的动态规划的过程了解得清楚的话，那么再复杂的问题，应该讲，你也能求解。

当子问题的解包含了公共资源的话，我们就可以知道，问题的性质一定是不具有最优子结构性质的

多了一个判段，本质还是查表，是动态规划。 可读性从上到下比基本动态规划的从下到上要好。

因为递归的开销，记忆法的时间常数比基本动态规划要高，对于矩阵链乘这个问题。

一个问题的(找出通过装配在Si，j 的最快路线)最优解包含了子问题(找过通过Si，j或Si，j的最快路线)的一个最优解，这个性质称为最优子结构。这是能否应用动态规划啊方法的标志之一.

proof: cut and paste方法证明 是最优的，假设不是，退出矛盾。

总结

动态规划

1.什么是动态规划方法？

解决多阶段决策最优化的过程称为动态规划方法.

和分治法一样，动态规划是通过组合子问题的解而解决整个问题的。

与分治法不同，动态规划适用于子问题不是独立的情况，也就是子问题包含公共的子问题。

动态规划算法对每个子问题只求解一次，将其保存在一张表(二维数组)中，从而避免每次遇到各个子问题时重新计算，本质上是空间换时间。

适用于最优化问题。

2.动态规划的基本步骤？

• 描述最优解的结构的特征。（一个问题的最优解包含子问题的解都是最优的，这个性质称为最优子结构性质）
• 递归定义最优解的值
• 按自底向上的方式计算出最优值
• 由计算出的结果，构造一个最优解

3.动态规划的要素

1. 所解问题必须具备最优子结构性质

   对于一个问题，怎样发现最优子结构性质？
   1.检查问题的解所面临的选择
   2.假定某种选择为一最优解
   3.分析这种选择将产生多少子问题
   4.证明子问题的解也是最优的
   eg:最长回文子串中
   1.选一个最长的回文串
   2.假设最长的长度为n时，是回文串
   3.2个子问题：去掉头或者尾。去掉一个肯定不是了，得去掉2个，去掉头尾也是回文子串。

2. 重叠子问题

   • 虽然问题分解后是否存在重叠子问题不是应用动态规划方法的必要前提，但存在重叠子问题应用动态规划方法能提高算法效率

3. 记忆法

   • 记忆法是动态规划方法的一种变种形式，它采用自顶向下计算最优解的值

4.相关算法/问题：

• 背包问题
• 最长回文子串(leetcode)
• 最优二叉树