动态规划和分治的区分

2018年2月9日 下午4:15

我参考了一些文章，例如：五大常用算法：分治、动态规划、贪心、回溯和分支界定 - CSDN博客。但是我觉得总结的并不是那么的容易理解。

我的理解从两个方面去描述：

1. 【主要】：数学上的前后结果规律是否存存在？以及我们找这个规律的过程，回花费我们做题时间的60~80%，足以体现出他的重要性
2. 【次要】：从解决的问题上来说。dp最后要的结果往往是一些具体的数值，比如说求最大最小等问题。在分治中，一般结果往往是一些“现象”，比如说排序等问题。

一般规律：

1. 这里的前后结果往往都会涉及多个前结果的组合，关键是我们如何找到有哪些组合，以及组合之间的关系！！
   1. eg：不等式数列_牛客网
   2. 这里就有四个不同前结果去组合表示下一个结果。

方法：

1. 举具体的例子🌰去测试，这个过程没啥技巧吧，就是不断地尝试。