我们通过理解算法背后常用的算法思想，进行归纳总结，并通过 LeetCode 练习来辅助理解和提升。
算法思想详解
在解决问题时，除了掌握具体的数据结构与算法，更重要的是理解其背后的通用算法思想。本系列将常见的算法思想归纳为以下几类：
- 分治算法：将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
- 动态规划算法：通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
- 贪心算法：保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。
- 二分法：分治算法重要的应用之一，比如二分查找。二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
- 搜索算法：主要包含 BFS、DFS。
- 回溯算法：Backtracking（回溯）属于 DFS。回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就”回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
相关文章
- 算法思想：二分法 —— 二分查找的正常实现、时间复杂度与各类变种题解
- 算法思想：贪心算法 —— 分配饼干、不重叠区间、股票收益等经典贪心题目
- 算法思想：分治算法 —— 给表达式加括号
- 算法思想：回溯算法 —— 排列、组合、子集、数独、N 皇后等经典题目
- 算法思想：动态规划算法 —— 斐波那契数列、矩阵路径、0-1 背包、股票交易、字符串编辑等专题
- 算法思想：搜索算法 —— BFS 与 DFS 的思想辨析及经典题目
系列导航
- 上一篇：图：AOE & 关键路径
- 下一篇：算法思想：二分法