1、分治法

  • 设计思想
    • 将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之

  • 适用条件

    • 该问题的规模缩小到一定的程度就可以容易地解决
    • 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
    • 利用该问题分解出的子问题的解可以合并为该问题的解；
    • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

  • 应用例子

    • 快速排序
      • 思路：
        • 1.通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小
        • 2.重复步骤1对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
      • 时间复杂度：O(nlogn)
    • 归并排序
      • 二分查找
        • 思路
          • 1.将数组分为n等份(算法中为2)，对各子数组递归调用归并排序
          • 2.等分为2份时为2路归并，最后子数组排序结束后，将元素合并起来，复制回原数组
          • 时间复杂度：O(nlogn)
    • 堆排序

2、动态规划法

  • 设计思想

    • 动态规划是一种将问题实例分解为更小的/相似的子问题，并存储子问题的解，使得每个子问题只求解一次，最终获得原问题的答案，以解决最优化问题的算法策略
    • 动态规划通过求解局部子问题的最优解来达到全局最优解

  • 解题步骤

    • I.找出最优解的性质，并刻划其结构特征。(最优子结构)
    • II.递归地定义最优值。
    • III.以自底向上的方式计算出最优值。
    • IV.根据计算最优值时得到的信息，构造最优解。

  • 适用条件

  • 应用例子

    • 经典数字三角形问题

    • 最大连续乘积子数组

      • 问题描述：任意取出数组中的若干个连续的数相乘，找出其中乘积最大的子数组
      • 解题思路：考虑到负数的存在，即负负得正的情况可能成为乘积最大的子数组，故需要同时并记录找出最大乘积和最小乘积

    • 背包问题

      • 问题描述：一共有n件物品，对每一件物品i都有两种选择，即装入背包或不装入。一件物品只能装一次且不能装入部分物品

3、回溯法

  • 设计思想

    • 把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
    • 递归和递推（迭代）

  • 解题步骤

    • 回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。
    • 剪枝函数包括两类：
        1. 使用约束函数，剪去不满足约束条件的路径；
      • 2.使用限界函数，剪去不能得到最优解的路径。

  • 适用条件

    • 图的深度优先搜索
    • 二叉树的后序遍历

  • 应用例子

    • 装载问题

    • 0-1背包问题

      • 问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

    • 八皇后

      • 迷宫问题

4、贪心算法

  • 设计思想

    • 指在对问题求解时，总是做出在当前看来是最好的选择

  • 解题步骤

    • 1.建立数学模型来描述问题；
    • 2.把求解的问题分成若干个子问题；
    • 3.对每一子问题求解，得到子问题的局部最优解；
    • 4.把子问题的局部最优解合成原来问题的一个解。

  • 适用条件

  • 应用例子

    • 活动选择问题
    • 钱币找零问题