目录

• 一、基础策略
• 二、图遍历
• 三、动态规划细分
• 四、图论算法
• 五、字符串算法
• 六、数据结构
• 七、搜索优化
• 八、智能优化
• 九、其他常用技巧

---

一、基础策略

算法名称	核心特征	主要应用场景
暴力枚举	遍历所有可能性，逐个验证	密码破解、穷举所有解
贪心算法	每步选局部最优，不回溯	活动选择、找零钱（部分场景）
分治法	分解为独立子问题，递归解决后合并	归并排序、快速排序
回溯法	DFS + 剪枝，尝试后回退撤销状态	N皇后、迷宫寻路、数独求解
动态规划	记录子问题解（查表），避免重复计算	背包问题、编辑距离、LCS
分支限界法	BFS/优先队列 + 界限剪枝，求最优解	旅行商问题、任务分配

---

二、图遍历

算法名称	核心特征	主要应用场景
深度优先搜索(DFS)	沿一条路径深入到底，回溯，使用栈/递归	连通性检测、拓扑排序
广度优先搜索(BFS)	层层推进，先访问所有邻居，使用队列	无权图最短路径、网络爬虫

---

三、动态规划细分

算法名称	核心特征	主要应用场景
线性DP	状态在一维/二维数组按顺序递推	LIS、LCS、最大子数组和
背包DP	在容量限制下选物品求最大价值	0/1背包、完全背包
区间DP	由小区间合并成大区间递推	矩阵链乘法、石子合并
树形DP	在树上做DFS后序遍历，子传父	树的直径、打家劫舍III
状态压缩DP	用二进制位表示集合状态	TSP、集合覆盖问题
数位DP	按十进制位逐位统计	统计1到n中不含某数字的个数

---

四、图论算法

算法名称	核心特征	主要应用场景
Dijkstra	贪心策略，优先队列，非负权	单源最短路径
Bellman-Ford	可处理负权边，检测负环	含负权边的单源最短路
Floyd	动态规划，多源，O(n³)	任意两点间最短路径
Kruskal	按边权排序 + 并查集判环	最小生成树
Prim	优先队列，按点扩展	最小生成树
拓扑排序	对有向无环图节点线性排序（Kahn/DFS）	课程表安排、编译依赖
Tarjan	强连通分量缩点	求强连通分量、缩点建图
网络流	求最大流量（Ford-Fulkerson/Dinic）	最大流、最小割、二分图匹配
匈牙利算法	增广路找最大匹配	二分图最大匹配

---

五、字符串算法

算法名称	核心特征	主要应用场景
KMP	利用前缀函数（next数组），线性匹配	单模式串匹配
Trie树	树形结构存储字符串集合，支持前缀查询	自动补全、单词搜索
Manacher	线性时间求最长回文子串	最长回文子串
AC自动机	Trie + KMP（fail指针），多模式匹配	敏感词过滤、多关键词搜索

---

六、数据结构

算法名称	核心特征	主要应用场景
并查集	集合合并与查询连通性，路径压缩	朋友圈、Kruskal、连通块
线段树	递归维护区间信息，支持区间查询/更新	区间最值、区间和、动态RMQ
树状数组	前缀查询 + 单点更新（lowbit操作）	逆序对、动态前缀和
单调栈	维护单调序列，找左右第一个更大/更小元素	最大矩形面积、接雨水
单调队列	维护窗口内单调序列	滑动窗口最值

---

七、搜索优化

算法名称	核心特征	主要应用场景
双向BFS	起点终点同时BFS，相遇时停止	单词接龙、八数码问题
A*搜索	带启发函数（f=g+h）的BFS	游戏寻路、路径规划
迭代加深	限制深度DFS，逐渐放宽	棋盘搜索、IDA*

---

八、智能优化

算法名称	核心特征	主要应用场景
模拟退火	概率接受较差解以跳出局部最优	函数最值、TSP近似解
遗传算法	选择、交叉、变异迭代进化	优化问题、神经网络结构搜索

---

九、其他常用技巧

算法名称	核心特征	主要应用场景
双指针	两个指针协同扫描数组	两数之和、链表判环
前缀和/差分	预处理O(1)区间查询 / O(1)区间加减	区间和、差分数组
快速幂	二分乘法，O(log n)计算幂次	a^b mod m、矩阵快速幂
扩展欧几里得	解线性同余方程，求逆元	求逆元、解模线性方程
素数筛	标记法批量筛素数（埃筛/欧拉筛）	求n以内所有素数
Miller-Rabin	大数概率性素性测试	大数素数判断