算法基本思想(笔记)

贪心算法

分治算法

• 总结
  实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
• 步骤
  分治法在每一层递归上都有三个步骤：
  step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
  step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
  step3 合并：将各个子问题的解合并为原问题的解。
• 常处理的问题
  （1）二分搜索
  （2）大整数乘法
  （3）Strassen矩阵乘法
  （4）棋盘覆盖
  （5）合并排序
  （6）快速排序
  （7）线性时间选择
  （8）最接近点对问题
  （9）循环赛日程表
  （10）汉诺塔

动态规划

回溯算法

枚举算法