本篇属于应头条'专栏精华'活动邀请，摘取的专栏《深入解读100道经典面试题》第1篇中的部分内容推荐给大家，更多详细内容需要大家进入专栏细读。
专栏共100篇，精选了被各大知名公司面试官反复采用的面试题，并且总结了针对这些面试题的常用思路和解决方案，极具实战意义。
查看'专栏简介'，戳这里'深入解读100道经典面试题'。
前言
今天这篇，我主要跟大家分享的是，在面试中遇到算法题，我们需要掌握六大算法范式，然后才能快速为算法问题构建高效的解决方案。
算法范式
常见的算法范式有：
1.暴力破解法
2.分治法
3.动态规划法
4.贪心算法
5.回溯法
6.分支限界法
暴力破解法
暴力破解法简单直接，根据问题声明的定义，找到所有可变化的因子，穷举所有可能解决问题的方法，逐个尝试。
所以，根据暴力破解法的定义，理论上讲任何问题都可以使用暴力破解法来解决，只是在实际应用中算法对时间和空间的需求则无法满足。
将暴力破解法应用于数据查找，由于查找比较次数与给定目标的规模直接相关，所以也称为线性查找。
分治法
分治法，即 '分而治之'，是将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些问题，然后再合并其结果，以得到原问题的解。
当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。这些规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题，规模变小后的问题其实是原问题的子问题。
动态规划法
动态规划的过程可以描述为多阶段最优化解决问题的过程，每一次的决策依赖于当前的状态，随即又引起状态的转移，以此类推在变化的状态中产生出决策序列。
动态规划算法通常基于一个递推公式及一个或多个初始状态，当前子问题的解将由上一次子问题的解推出。使用动态规划来解题通常只需要多项式时间复杂度，所以会比回溯法、暴力法等要快许多。
动态规划方法中的关键词包括：阶段、状态、决策、递推关系。
动态规划首先将待求解的问题分解为若干个子问题（阶段），按顺序求解子问题。前一子问题的解为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。以此类推解决各子问题，最后一个子问题的解就是初始问题的解。
动态规划与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子问题的求解是建立在上一个子问题的解的基础上，进行进一步的求解）。
贪心算法
所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。贪心策略适用的前提是：局部最优策略能导致产生全局最优解。所以实际上，贪心算法适用的情况很少。
贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
回溯法
回溯法描述了一种选优搜索过程，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的方法称为回溯法，而满足回溯条件的某个状态的点称为 '回溯点'。
回溯法可以理解为隐式的深度优先搜索算法。其在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度探索解空间树。
当探索到某一节点时，要先判断该节点是否包含问题的解，如果包含，就从该节点出发继续探索下去，如果该节点不包含问题的解，则逐层向其祖先节点回溯。
许多复杂的，规模较大的问题都可以使用回溯法，有 '通用解题方法' 的美称。
分支限界法
类似于回溯法，分支限界法也是一种在问题的解空间树上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。
回溯法的求解目标是找出树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
所谓 '分支' 就是采用广度优先搜索算法，依次搜索节点的所有分支，抛弃不满足约束条件的节点，然后从余下的节点中选择一个节点作为下一个搜索节点继续搜索。
由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
总结
本篇我们主要是摘取了专栏中的部分内容，简单了解了六大算法范式，更多详细内容欢迎大家到专栏的第1篇名企面试题精选，掌握六大算法范式，再也不担心被问到算法题细读。
关于专栏
专栏共有100期课程，笔者精选了被各大知名公司面试官反复采用的面试题，题目包括了数据结构算法、系统设计、编程语言、数据库、操作系统等方向，欢迎大家前往阅读。
您得到的收获将是掌握这些精选面试题的常用思路和解决方案，极具实战意义，对于跳槽，晋升，拿到更高水平的offer将带来极大的帮助。
如果觉得《掌握这六大算法范式 再也不担心面试被问到算法题》对你有帮助，请点赞、收藏，并留下你的观点哦！
