递归与分治

关于分治(Divide and Conquer)，简单来说，”化大为小，分而治之“。之所以没有“小事化了”，是因为在击破“小事”之后，还需要按照自底向上的方式合并“小事的解“，最终得出”大事的解“。与分治相伴而生的递归函数，是描述分治思想的天然工具，其两个要素分别是边界条件和递归方程。如果将求解一个递归问题比作走迷宫，则边界条件给了一个出口，递归方程给了”走“的方式。将一个递归问题写成递归程序，如何看待程序的优缺点呢?

  • 优点：结构清晰，可读性强，易用数学归纳法证明算法的正确性。

  • 缺点：递归算法运行效率低，时间消耗多，存储空间占用多。

要在递归算法中消除递归调用，有三种方式：

  • 利用自定义栈模拟系统递归调用栈(脑补数据结构教材上那些有pop()和push()函数的伪代码)。

  • 用递推实现递归函数(打印斐波那契数列的多种方法)

  • 尾递归(不常用)

结束战术层面的讨论回到战略，分治法的适用条件是什么？(四个条件来自Boss总结)

  1. 原问题规模缩小到一定程度可以容易地解决（可分性）

  2. 原问题可分解为若干个规模较小的相同问题（子结构性质）

  3. 子问题的解可以合并为原问题的解(可合并性)

  4. 子问题相互独立

条件4归到条件2的子结构性质可能相对合适，这样要求子问题：规模较小，相同，独立。在具体分解的时候的一个trick是平衡子问题，意思是使得子问题规模大致相等比规模不等做法好。

贪心策略（自顶向下）

使用贪心算法的两个要素：

  • 贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来达到。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

  • 最优子结构性质：一个问题的最优解包含其子问题的最优解

动态规划（自底向上）

使用动态规划的两个要素：

  • 最优子结构性质

  • 重叠子问题性质

设计动态规划算法的步骤（最优解和最优值的概念）：

1. 找出最优解的性质，刻画结构特征。

2. 递归地定义最优值

3. 计算最优值

4. 根据计算过程，构造最优解

回溯法

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索

总结

虽然算法思想就是这样，但是每隔一段时间重新翻看，都会有更深刻的认识和理解上的提升。在利用这些思想设计算法的时候，证明算法的正确性是最有挑战性的问题。据自己观察，一些同学利用问题之间的类比然后得到相似算法，也是一种有效快速的方式。自己从来没有奢望能够深刻领会到思想的精髓，只是希望在日积月累中提升自己的算法设计内功。