动态规划

​ 动态规划一般来说和分治有点类似都是让他们去处理相同的子问题，但是在动态规划里面你会遇到更多的相同子问题。然后我们就会导致很多的重复计算，所以一般我们可以使用递归来完成一个动态规划要完成的任务，但是这样一般会重复计算很多东西，所以动态规划一般就增加了一些矩阵来存放上一次计算的结果。

​ 例如斐波那契数列，这个如果我们直接使用地柜计算的话，我们会很多重复计算。然后当我们要使用一个阵列计算的时候我们在每一次计算之前我们都需要进行一次判断看看我们目前的结果是不是已经被计算了，如果计算了就相当于查表直接获取答案，否则我们才开始计算。

​ 状态：状态就是对于每一个字问题都可以使用一个数字 n 来描述这个子问题，如果状态相同就说明他们的答案相同。

​ 状态也可以有很多维度，例如排列组合就可以使用二维的，距离使用三维的，所谓的维度就是影响这个子问题的因素，也就是上面的那个 n 以及其他自定义的 j 等等！

​ 状态转移方程：就是使用当前的状态来获取其他的状态。

​ 一般状态转移方程可以使用 top down 也可使用 bottom up 方法。

​ 给一个例子：现在有红 绿 蓝 三种颜色的油漆图一面墙，这面墙 红绿 和 绿蓝不能相邻问共有多少中涂色的方法。

​ 状态：定义长度为 n 的时候的涂色的方法数，然后出事值就是当 n 等于 1 的时候涂色的方法就是三种。但是这样我们发现很难写出状态方程，所以我们就再添加一个维度。第二个维度的意思就是颜色。

于是就可以得到这样的状态转移方程。看起来稍微有点复杂。而我们最后求结果就是

另外一个例子就是骨牌的问题，这个问题就是费时数列的问题，但是我们需要自己进行研究开始的几种情况。