算法设计技巧
五大常用算法
分治法
分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多算法的基础，比如排序算法(快排，归并排序)……
适用情况：
分治法所能解决的问题一般具有一些几个特征：
（1）该问题的规模缩小到一定程度就可以容易地解决。
（2）该问题可以分解成为若干个规模较小的相同问题，即该问题具备最优子结构性质。
（3）利用该问题分解出的子问题的解可以合并为该问题的解。
（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加。
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用。
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
可用分治法的经典问题：
（1）二分查找
（2）大整数乘法
（3）合并排序
（4）快速排序
还有很多，遇到问题在列出来。
动态规划(dynamic programming)
动态规划常常适用于有重复子问题和最优子结构性质的问题，动态规划方法所消耗时间往往元小于朴素解法。
基本思想与分治法类似，也就是将带求解的问题分解成为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
与分治法最大的区别：适用于动态规划法求解的问题，经分解后得到的子问题往往不是相互独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步求解）。
适用情况：
能采用动态规划求解的问题的一般要有3个性质：
（1）最优化原理：如果问题的最优解所包含的字问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是DP适用的必要条件，但是如果缺少这条性质，则DP比其他算法没有了优势）。
回溯法(backtracking)
回溯法是一种暴力搜寻法，是一种可以找出所有(或部分)解的一般性算法，尤其适用于约束满足问题。
许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法的美称。
回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题答案。
回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
- 找到一个可能存在的正确答案
- 在尝试了所有可能的分步方法后宣告该问题没有答案
教科书般的用例：N个皇后问题。
最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。
LeetCode的一个系列回溯法的题：
39.Combination Sum
40.Combination Sum II
216.Combination Sum III
还存在337.Combination Sum IV,不过回溯法会很慢，LeetCode直接超时，但用动态规划保存已计算的值，会非常的快。
贪婪法
贪婪算法分阶段地工作，每一个阶段，可以认为是所做决定是最好的，而不考虑将来的结果。通常，这意味着选择的是某个局部最优。当算法结束时，希望局部最优等于全局最优。如果是这样的话，算法是正确的；否则，算法得到的是一个次最优解。
对于采用的贪心策略一定要仔细分析其是否满足无后效性。
这个算法不太熟，练习不到位，刷几波LeetCode再来做笔记。
分支限界法
与回溯法有点相像，但不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
遇到题了再来朴充。
最后附上学习地址红脸书生