一、动态规划法与分治法
1、相同点:两者相似,通过合并多个子问题的解来解决整体问题。
2、区别:
(1)、分治法是把大问题分解成一些相互独立的子问题,
递归的求解这些子问题,然后将他们合并来得到整个问题的解。
(2)、动态规划法是通过组合子问题的解来解决整个大问题。
各个子问题不是独立的,即各个子问题包含公共子问题。
(避免遇到子问题的重复求解)。
" 动态规划法 " 详述链接:【算法设计与分析】4、动态规划法
" 分治法 " 详述链接:【算法设计与分析】5、分治法
二、动态规划法与贪心法
1、贪心法通常用于求解最优化问题,即量的最大化或最小化。
2、贪心法不像动态规划法,其通常包含一个用以寻找局部最优解的迭代过程。在某些实例中,这些局部最优解转变了全局最优解,在另外一些情况下,则无法找到最优解。
" 动态规划法 " 详述链接:【算法设计与分析】4、动态规划法
" 贪心法 "详述链接:【算法设计与分析】3、贪心法