不知道你是怎么理解分治法和动态规划法的。
我原来一直以为，这是两种算法，但奇怪的是，这两种算法能够解决很多问题，比如，归并排序，0-1背包问题等等。
他们的算法明明不一样啊。
还有明明都是分治算法，为什么时间复杂度还不一样？
到底是哪里理解错了呢？
其实真正理解错误的是，分治法和动态规划法并不是算法。
换句话说就是分治法和动态规划法是两种设计算法的方法，而不是算法本身。
在弄清楚了这一点之后，再来看这两个方法也就能够解释为什么这两种方法能够解决问题很多种问题了。
因为根据实际问题，分析和哪种算法设计思路相近就选择使用哪种思路。
扩展一下，其实贪心算法、分治界限法和回溯法也和上面说的一样，他们都是算法设计的思路。
分治法
设计思路：
（1）分解；
（2）求解；
（3）合并。
动态规划法
设计思路：
（1）找到最优性质，并刻画其特征；
（2）递归地定义最优解的值；
（3）以自底向上的方式计算出最优值；
（4）根据计算最优值时得到的信息，构造一个最优解。
下面分别举一个例子：
归并排序（分治法）
（1）分解，将n个元素分成俩拨，一拨是1 ～ n/2，另一拨是 n/2+1 ～ n；
（2）求解，将这俩拨分别排序，分别再进行分解成俩拨，直到只涉及两个数的排序；
（3）合并，将求解的结果进行合并。
0-1背包问题（动态规划法）
0-1背包问题，指的是要么放进背包要么不放进背包，不存在放半个的情况。
当背包重量可承受17的重量，能够放入背包最大的价值是多少？
（1）找到最优性质，刻画其特征，当放入某个物品之后，剩余的重量去找下一个可以放入的物品，使其价值最大，反复这个操作，直到找到价值最高的组合；
（2）递归定义最优解；
（3）计算背包问题的最优解，如下图，一行一行计算最大可承载重量，所能够放入的最大价值；
（4）根据计算结果构造问题最优解，在得出这张表之后，计算背包是如何存放的，最优值是24，因为21（第4行，第18列）和24（第5行，第18列）不相等（可以理解为放5号物品和不放5号物品价值不同）,说明是放入了5号物品，减去5号物品的价值13，那么1-4号物品的最大价值应该是11，重量是8，因为10（第3行，第10列）和11（第4行，第10列）不相等（可以理解为放4号物品和不放4号物品价值不同），意味着放入了4号物品，减去价值11和重量8，发现结果为0，说明背包里没有放其他的物品，到此背包的最优解得出了，就是当背包最大可承载重量为17时只放入物品4和物品5，获得的价值最高。
原文：https://www.cnblogs.com/xiaojun-9/p/14839142.html