五大算法

一．分治算法(DC)

1. 基本思想

将一个问题，分解为多个子问题，递归地解决子问题，最终合并为原问题的解

2. 适用情况

   • 问题分解为小问题后容易解决
   • 分解后的小问题的解可以合并为原问题的解
   • 小问题之间互相独立

3. 解题步骤

   • 把原问题分解为若干子问题；
   • 递归求解每个子问题的解；
   • 合并子问题的解；

4. 实例

   • 合并排序
   • 股票买卖
   • 计算逆序对数
   • 二分法找指定元素

二．动态规划(DP)

1. 基本思想

将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息

2. 适用情况

   • 最优化原理：问题的最优解所包含的子问题的解也是最优的，即最优子结构
   • 无后效性：某个状态一旦确定，就不受以后决策的影响
   • 有重叠子问题

3. 解题步骤

   • 分析最优解的性质，并刻画其结构特征。
   • 递归的定义最优解。
   • 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
   • 根据计算最优值时得到的信息，构造问题的最优解

4. 实例

   • 斐波那契数列第n项
   • 拾取硬币
   • 矩阵连乘
   • 0/1背包

三．贪心算法

1. 基本思想

不从总体最优考虑，仅考虑局部最优解，问题必须具备后无效性

2. 适用情况

   • 局部最优策略能导致全局最优解
   • 子问题具备无后效性

3. 解题步骤

   • 将问题分解为多个子问题
   • 得到问题的局部最优解
   • 合并子问题的局部最优解

4. 实例

   • 硬币找零
   • 部分背包问题
   • 哈夫曼树和哈夫曼编码
   • 最小生成树(prim&kruskal)
   • 最短路径(dijkstra)

四．回溯法

1. 基本思想

选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间

2. 适用情况

   • 问题需要求出所有解

3. 解题步骤

   • 确定解空间
   • 确定结点的扩展搜索规则
   • 深度优先方式搜索解空间，用剪枝函数避免无效搜索

4. 实例

   • N皇后问题

五．分支界限法

1. 基本思想

   • 与回溯法类似，也是在解空间里搜索，不同的是，回溯法寻找所有解，分支界限法搜索一个解或者最优解
   • 分支：广度优先搜索策略，或者最小耗费优先
   • 搜索方式：FIFO、LIFO、分支界限搜索算法

2. 适用情况

   • 问题需要求出一个解或者最优解