动态规划与分治法

算法中，动态规划和分治算法是属于两种算法思想，他们有相同点和不同点：

相同点：
1，两者都是将大问题分解成若干个小问题，
2，两者都是依赖于小问题的解决，来解决上一级较大问题

不同点：
1，分治法往往用到递归计算，自上而下计算，而动态规划则直接自底向上计算
2，分治大的小问题在递归的过程中可能会被反复计算，动态规划中的小问题计算后被存储，下次再碰到时直接调用、
3，分治法的小问题的解只使用一次，动态规划的小问题的解存储以备大问题求解时反复调用

动态规划的一般构造条件：
1，存在最优子结构：下一级的最优解可以作为上一级最优解的基础

2，存在重复子问题：许多子问题的解会多次被调用（效率）

构造方法：
从子问题出发，自底向上，构造最优解，同时需要适配合适的数据结构存储子问题最优解

Paste_Image.png Paste_Image.png Paste_Image.png Paste_Image.png Paste_Image.png Paste_Image.png Paste_Image.png