分而治之法与dynamic规划的区别
Divide and Conquer Algorithms和Dynamic Programming Algorithms什么区别？ 这两个词有什么不同？ 我不明白他们之间的区别。
请举一个简单的例子来解释两者之间的区别，以及它们看起来相似的原因。
分而治之
分而治之，将问题分解为子问题，recursion地征服每个子问题，并结合这些解决scheme。
dynamic编程
dynamic规划是解决重叠子问题的技术。 每个子问题只解决一次，每个子问题的结果都存储在一个表（通常实现为一个数组或一个散列表）中，以备将来参考。 这些子解决scheme可以用来获得原始解决scheme，存储子问题解决scheme的技术被称为memoization。
你可能会想到DP = recursion + re-use
理解差异的一个典型例子是看到这两种方法获得第n个斐波纳契数。 检查来自MIT的这个材料 。
编辑
分而治之的方法 
dynamic规划方法 
有时在recursion编程时，可能会多次调用具有相同参数的函数，这是不必要的。
着名的例子斐波那契数字：
index: 1,2,3,4,5,6... Fibonacci number: 1,1,2,3,5,8... function F(n) { if (n < 3) return 1 else return F(n-1) + F(n-2) }
让我们运行F（5）：
F(5) = F(4) + F(3) = {F(3)+F(2)} + {F(2)+F(1)} = {[F(2)+F(1)]+1} + {1+1} = 1+1+1+1+1
所以我们叫：1次F（4）2次F（3）3次F（2）2次F（1）
dynamic编程方法：如果多次调用同一个参数的函数，将结果保存到一个variables中，以便下一次直接访问它。 迭代的方式：
if (n==1 || n==2) return 1 else f1=1, f2=1 for i=3 to n f = f1 + f2 f1 = f2 f2 = f
我们再次调用F（5）：
fibo1 = 1 fibo2 = 1 fibo3 = (fibo1 + fibo2) = 1 + 1 = 2 fibo4 = (fibo2 + fibo3) = 1 + 2 = 3 fibo5 = (fibo3 + fibo4) = 2 + 3 = 5
正如你所看到的，只要你需要多次调用，就可以访问相应的variables来获取值，而不是重新计算它。
顺便说一下，dynamic编程并不意味着将recursion代码转换为迭代代码。 如果需要recursion代码，也可以将子结果保存到variables中。 在这种情况下，这种技术被称为memoization。 对于我们的例子，看起来像这样：
// declare and initialize a dictionary var dict = new Dictionary<int,int>(); for i=1 to n dict[i] = -1 function F(n) { if (n < 3) return 1 else { if (dict[n] == -1) dict[n] = F(n-1) + F(n-2) return dict[n] } }
所以与分而治之的关系是D＆Dalgorithm依赖于recursion。 而他们的一些版本有这个“具有相同参数问题的多个函数调用”。 search“matrix链乘法”和“最长的公共子序列”这样的例子，其中需要DP来改善D＆Dalgorithm的T（n）。
分而治之和dynamic规划的另一个区别是：
分而治之：
- 在子问题上有更多的工作，因此有更多的时间消耗。
- 在分而治之中，子问题是相互独立的。
dynamic编程：
- 只解决一次子问题，然后将其存储在表中。
- 在dynamic编程中，子问题不是独立的。
我假设你已经阅读了维基百科和其他学术资源，所以我不会回收这些信息。 我还必须告诫说，我不是一个计算机科学专家，但我会分享我的两个分，我的理解这些话题…
dynamic编程
将问题分解成离散的子问题。 Fibonacci序列的recursionalgorithm是dynamic规划的一个例子，因为它通过首先求解fib（n-1）来求解fib（n）。 为了解决原来的问题，解决了另一个问题。
分而治之
这些algorithm通常解决类似的问题，然后把它们放在一起。 Mergesort是分而治之的典型例子。 这个例子和斐波那契的例子之间的主要区别在于，在合并中，分割可以（理论上）是任意的，不pipe你如何分割，你仍然是合并和sorting。 不pipe你怎样划分，都需要做相同的工作来合并数组。 求解fib（52）需要比求解fib（2） 更多的步骤 。
我把“ Divide & Conquer而Divide & Conquer看作recursion方法，把“ Dynamic Programming看作表格填充。
例如， Merge Sort是一个Divide & Conqueralgorithm，因为在每一步中，你将数组分割成两半，recursion调用Merge Sort ，然后合并它们。
Knapsack是一个Dynamic Programmingalgorithm，因为你正在填充表示整个背包的子问题的最佳解决scheme的表格。 表格中的每个条目对应于给定项目1-j的重量包中可以携带的最大值。
