算法练习（特辑）设计算法的常用思想

1、递推法

• 递推的思想是把一个复杂的庞大的计算过程转换为简单过程的多次重复，每一次推导的结果作为下一次推导的开始。

2、递归法

• 递归算法实际上是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最终获得最终的解。所以相较于递推而言，递归算法的范畴更小，要求子问题跟父问题的结构相同。而递推思想从概念上并没有这样的约束。
• 递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

3、贪心算法

• 用贪心法设计算法的特点是一步一步地进行，以当前情况为基础根据某个优化测度做最优选择。它省去了为找到最优解要穷尽所有可能而必须耗费的大量时间。
• 贪心算法的实现过程就是从问题的一个初始解出发，每一次都作出「当前最优」的选择，直至遇到局部极值点。

4、分治法

• 分治法是把一个复杂问题分成2个或更多个相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

5、动态规划法(DP)

• 动态规划同样需要将问题划分为多个子问题，但是子问题之间往往不是互相独立的。当前子问题的解可看作是前多个阶段问题的完整总结。因此这就需要在在子问题求解的过程中进行多阶段的决策，同时当前阶段之前的决策都能够构成一种最优的子结构。

6、回溯法

• 回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
• 简单来说，回溯的过程就是在做出下一步选择之前，先对每一种可能进行试探；只有当可能性存在时才会向前迈进，倘若所有选择都不可能，那么则向后退回原来的位置，重新选择

7、枚举

• 其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。

8、核心思想：把一个复杂问题分解成可以解决的小问题，如果是从上到下，把N个问题分解成N-1个问题，就用递归；如果是从下到上，从0开始推导到N就用递推或DP。