算法策略

分治法

基本思路

分解->解决->合并

基本要求（步骤）

• 该问题地规模缩小到一定的程度就可以容易地解决
• 该问题可以分解成为若干个规模较小的相同问题
• 利用该问题分解除的子问题的解可以合并为该问题的解（使用递归求解）
• 该问题所分解出的各个子问题是相互独立的

递归技术

二分法查找

回溯法

基本思想

以深度搜索优先来寻找目标，如果寻找目标，就退回一步重新选择

贪心法

基本思想

• 并不从整体上加以考虑，他所做的每步选择只是当前步骤的局部最优选择
• 耗时少，一般可以快速得到满意的解，但得不到最优解

经典实例

0/1 背包问题

动态规划法

基本思想

• 与分治法类似，但不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
• 动态规划法一般用一种查表的方式来解决问题