1 先把细节全部都记下来
3 反复完之后,化繁为简,浓缩成就一点
动态规划的本质就是将一个复杂的问题,分解成重复性子问题.
分治,回溯,递归,动态规划都差不多,只是一些小的细节问题
分治 Divide & Conquer ;它是递归的一种特殊形式,因为复杂的问题,都有很多重复性子问题,分别运算,再返回结果
动态规划Dynamic Programming:wiki中DP的定义是需要进行分治,DP和分治有内在联系,和分治的区别(动态规划问题是让求最优解,最大值,最少的方式, 所以在中间部分不需要保存所有的状态,只需要保存最优的状态,还要证明,如果每一步存最优的值,最后可以推导出全局最优的值, 所以引入了两个,一个是有所谓的缓存,或者是状态的存储数组,第二个就是每一步的话都会把次优的状态淘汰掉,只保留在这一步里面最优或者较优的一些状态推导出全局最优)
动态规划DP和递归或者分治,没有根本的区别,(关键看有无最优子结构,如果没有最优子结构,说明所有的问题都需要计算一遍,同时把结果合并在一起,传统意义上就称之为分治)
差异性:最优子结构,中途可以淘汰次优解,当然也必须淘汰次优解
这也是为什么DP很多时候我们把它翻译为动态递推就是这个原因