1.动态规划和分治的共同点

都是将规模较大的问题划分为多个规模较小的子问题，求得子问题的解。再将子问题的解合并最终得到大问题的解。

2.动态规划和分治的不同点

• 动态规划：各个子问题不独立、子问题之间存在依赖关系。在求解过程中会将已经计算过的子问题结果保存，当再次遇到相同或相似的子问题时，便不会再次计算，直接利用已经保存的子问题结果即可。即使用迭代来做。
• 分治：各个子问题独立、子问题之间不存在依赖关系，每个子问题都需要独立求解，而不是像动态规划那样有机会可以利用已经求解过的子问题的解。即使用递归来做。

3.例子

在求解斐波拉西数列时，若使用分治的方式会存在节点被重复计算的情况。即在递归过程中fib(4)会被计算两次。若使用动态规划的方式，会将第一次遇到的fib(4)存下来，当再次遇到fib(4)时便不再计算，直接拿第一次计算的结果用即可。也就是fib(4)只会被计算一次。

//递归方式  分治思想 不记录子问题的结果
int fib(int n){
    //递归结束条件
    if(n<=0) return 0;
    if(n == 1) return 1;
    return fib(n-1)+fib(n-2);//每次都要计算子问题
}

//动态规划方式  需要记录子问题的结果
int fib(int n){
    vector<int> temp(n+1);//用于记录子问题的结果
    temp[0] = 0;
    temp[1] = 1;
    for(int i = 2;i <= n;i++){
        temp[i] = temp[i-1] + temp[i-2];//求fib(i)时用到了fib(i-1)和fib(i-2)的结果 并没有去计算fib(i-1)和fib(i-2)
    }
    return temp[n];
}