前言
常见算法及其思想与对应题目总结
正文
一. 分治算法
1.1 基本思想与适用场景
分治法，顾名思义，即分而治之，适用于当一个问题很复杂，难以解决，但是可以分解为许多容易解决的相似子问题，且子问题解合并起来即为原复杂问题解时的情况
从上面的描述中我们可以提取出分治法适用的几个要点：
- 原问题可分解为许多相似子问题
- 子问题解可合并为原问题解
- 子问题独立，即子问题之间无公共子问题（非必须，涉及到分治法效率问题，若子问题之间不独立，分治法效率较低，一般使用动态规划）
上面的要点2是适用分治法的关键，也是判断一个问题是否可以使用分治法解决的关键，如果一个问题不满足第二条，可以考虑使用贪心或者动态规划；从其特征可以看出，分治法通常伴随着递归（因为有相似子问题，明显的递归解决思路），递归也是我们通常解决此类问题的常用手段
1.2 应用举例
- 二分搜索
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
1.3 参考链接
- https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html
二. 动态规划
1.1 基本思想与适用场景
动态算法的核心是记住已经求过的解，在已知解的基础上继续求解；记住求解的方式有两种：一是自顶向下的备忘录法，二是自底向上
自顶向下一般涉及到递归，通常需要传递一个容器来存储结果，在分治算法中也提到了，当子问题不独立时，此时可以考虑使用动态规划（效率问题，用空间换取时间），该容器存储的结果实际上就是用于结束重复的递归计算
自底向上即最开始就从子问题计算起，逐步往上，相当于递归的拆解（循环）
参见动态规划的意义，将动态规划视为状态的转移来进行理解和区别
特征：
- 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到–最优子结构
- 不管之前这个状态是如何得到的–无后效性
1.2 应用举例
- Fibonacci数列问题
- 钢条切割问题
- 小朋友过桥问题
- 背包模型
- 最长单调子序列
- 最大M子段和
- 线性模型
1.3 参考链接
-
https://blog.csdn.net/u013309870/article/details/75193592
-
https://www.zhihu.com/question/23995189
