概述
算法中有两个非常重要的思想分别是:分治策略和动态规划。它们通常可以将处理复杂的问题,转化为处理N个相关的子问题。通过这种方式,给予人们清晰的思路的同时,降低处理问题的难度。这一篇文章我们来介绍分治策略,并给出几个经典的算法来进行展示。
简介
分治策略中,往往是通过递归去求解问题,并在每层递归中应用如下三个步骤:
- 分解:将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。
- 解决:递归的求解子问题,如果子问题的规模足够小,则停止递归,直接求解。
- 合并:讲子问题的解组合成原问题的解。