在这篇blog中我将通过费氏数列引入，然后介绍动态规划的概念，以及它和分治苏纳法的区别与联系。然后使用动态规划的思想来解决以下四个非常著名的问题：

同时也是为了自己做记录，防止以后自己忘记。

费氏数列是由0，1开始，之后的每一项等于前两项之和： 0，1，1，2，3，5，8，13，21，34，55，89，144…

但是存在效率较低的问题： 因为存在大量的重复计算，比如说，如上图所示，f(n-4)就出现了多次计算的情况。

借助中间变量存储结果，然后就可以消除重复计算。

伪代码： 算法主要思想：

我认为，我所见过的大多数动态规划问题似乎都用到了我们常说的的空间换时间和分治的思想。

这里借用我们上课的时候老师给的例子，可以很明显的看到，这里不同的矩阵相乘的顺序得到的最终的时间复杂度师有很大不同的。我们目标是找到时间复杂度最低的连乘次数。

这种方法的时间复杂度非常高，完全是指数级别的，具体的推导这里不在赘述。

思路： 计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系： 计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数C[i,j]，则原问题的最优值为C[1,n]