常用算法特点总结
| 适用场景 | 关键词 | 步骤 | 常见案例 | |
| 分治法 | 递归，left和right | 1.分解 2.求解 3.合并 |
归并排序、最大字段和 | |
| 动态规划法 | 1.最优子机构 2.重叠子问题。查表替换递归，提高算法效率。 |
递推一般优于递归 | 1.最优解定义，选或不选 2.递归 3.自底而上计算最优解（建表） 4.查表找最优解 |
0-1背包、最长公共子序列 |
| 贪心法 | 1.最优子结构 2.贪心选择性；整体最优通过局部最优 |
局部最优 | 1.数组排序，定起点 2.按照数组顺序，递归或迭代 |
活动安排、背包问题、钱币找零 |
| 回溯法 | 深度优先，限界函数，搜索空间，剪枝 ，全局最优解 |
1.外部循环（解空间） 2.判断条件，满足:下一个 3.判断条件，不满足：清除上一个 |
0-1背包、n皇后问题 | |
| 分支限界法 | 广度优先，最小耗费优先，一个解 | |||
| 概率算法 | 快速，两次结果可能不同，容许小概率 错误 |
数值概率、蒙特卡洛、拉斯维加斯 、舍伍德算法 |
||
| 近似算法 | 放弃最优解，追求降低时间复杂度 | |||