算法模板速查手册
大约 18 分钟
开篇：这份手册用 Python 写成，因为算法模板 Python 最简洁
你可能会问：这是一个 Java 技术博客，为什么这篇文章全是 Python？
原因很简单：算法模板追求的是"最短路径表达核心逻辑"，Python 的语法糖（列表推导、元组解包、内置 heapq/bisect/Counter 等）能让模板代码比 Java 短 2-3 倍，更容易记忆和手写。面试时用 Python 写算法题也是完全被接受的。
这份手册不是按叙事逻辑组织的教程，而是一份速查参考。每个算法模板前面都有一行"识别特征"——帮你在看到一道新题时快速判断该套用哪个模板。建议收藏后按需查阅，而不是从头读到尾。
一、Python 常用语法速查
刷题时反复用到的语法和内置函数，放在最前面方便随时翻。
1.1 常用内置函数
# reduce：对序列做累积运算
from functools import reduce
reduce(lambda x, y: x * y, ns) # 数组元素连乘
reduce(lambda x, y: x + y, ns) # 数组元素求和
# 记忆化搜索（面试中的 DFS + 剪枝利器）
@functools.lru_cache(None)
def helper(state):
...
helper.cache_clear() # 清除缓存
tuple(ns) # list 不可 hash，转 tuple 才能做 lru_cache 的参数
# 大根堆（Python 的 heapq 只有小根堆，取负数模拟大根堆）
q = list(map(lambda x: -x, ns))
heapq.heapify(q)
key = -heapq.heappop(q)
# filter 过滤
filter(lambda x: 2 < x < 10 and x % 2 == 0, range(18))
# divmod 同时取商和余数
div, mod = divmod(sum(ns), 4)
# 多关键字排序（第一个降序，第二个升序）
sorted(pss, key=lambda x: [x[0], -x[1]])1.2 字符串 str 常用方法
split(sep=None, maxsplit=-1) # 按 sep 分割
strip([chars]) # 去除首尾字符，默认空白
join(iterable) # 拼接：','.join(['a','b']) => "a,b"
replace(old, new[, count]) # 替换
count(sub[, start[, end]]) # 统计子串出现次数
startswith(prefix[, start[, end]]) # 前缀判断
endswith(suffix[, start[, end]]) # 后缀判断
cs in chrs # 包含判断1.3 deque 双端队列
from collections import deque
q = deque([iterable[, maxlen]])
q.append(val) # 右端添加
q.appendleft(val) # 左端添加
q.pop() # 右端弹出
q.popleft() # 左端弹出
q.reverse() # 反转
q.rotate(n=1) # 右端 n 个元素移到左端1.4 list 常用方法
lst.sort(*, key=None, reverse=False)
lst.append(val) # 尾部追加
lst.pop(val=lst[-1]) # 默认弹出末尾
lst.remove(val) # 移除第一个匹配的 val
lst.insert(i, val) # 在位置 i 插入 val
lst.reverse() # 原地反转
lst.count(val) # 统计 val 出现次数
lst.clear() # 清空1.5 dict 常用方法
from collections import defaultdict
d = defaultdict(lambda: value) # 取不存在的 key 时返回默认值
d.get(key[, default]) # 安全取值
d.setdefault(key[, default]) # 不存在则设置默认值
d.pop(key[, default]) # 删除并返回
d.update([other]) # 批量更新
d.keys() / d.values() / d.items() # 视图
dict1 == dict2 # 字典相等比较（滑窗时可用）1.6 set 常用方法
s = set()
s.add(elem) # 添加
s.update(*others) # 批量添加
s.discard(elem) # 删除（不存在不报错）
s.clear() # 清空1.7 heapq 堆操作
import heapq
heap = []
heapq.heappush(heap, item) # 入堆
heapq.heappop(heap) # 弹出最小值
heap[0] # 查看最小值（不弹出）
heapq.heapify(x) # 列表转堆，O(n)
heapq.heappoppush(heap, item) # 弹出最小值并入新值
heapq.nlargest(n, iterable, key=None) # 最大的 n 个
heapq.nsmallest(n, iterable, key=None) # 最小的 n 个1.8 bisect 二分查找
import bisect
bisect.bisect_left(a, x, lo=0, hi=len(a)) # 左边界
bisect.bisect_right(a, x, lo=0, hi=len(a)) # 右边界
bisect.insort_left(a, x, lo=0, hi=len(a)) # 二分插入到左侧
bisect.insort_right(a, x, lo=0, hi=len(a)) # 二分插入到右侧1.9 位运算
& # 按位与
| # 按位或
^ # 按位异或
<< # 左移
>> # 右移
~ # 按位取反
# 整数集合的位运算技巧（用整数的 bit 位表示集合）
vstd | (1 << i) # 访问 i（加入集合）
vstd & ~(1 << i) # 离开 i（从集合移除）
not vstd & (1 << i) # 不包含 i
A | B # 并集
A & B # 交集
(1 << n) - 1 # 全集（n 个元素）
((1 << n) - 1) ^ A # 补集
(A & B) == B # B 是 A 的子集
A & (A - 1) == 0 # 判断是否是 2 的幂
n &= (n - 1) # 最低位的 1 变为 0
A & (-A) # 取最低位的 1（lowbit）1.10 正则表达式
import re
# ^ 匹配字符串开头
# [+-] 匹配 + 或 -
# ? 前一个字符可有可无
# \d 一个数字
# + 前一个字符的 1 个或多个
# \D 一个非数字字符
# * 前一个字符的 0 个或多个
matches = re.match(r'[ ]*([+-]?\d+)', s)二、动态规划模板
识别特征：题目问"最少/最多/方案数/是否可行"，且问题可以拆分成子问题，子问题之间有重叠。
动态规划的核心是状态定义 + 状态转移方程。模板只是骨架，关键在于根据题意定义好 dp[i] 或 dp[i][j] 代表什么。
2.1 背包问题
背包是 DP 中最经典的一类，分三种：
0-1 背包（每个物品只能选一次）
识别特征：给定一组物品和容量限制，每个物品只能用一次，求最大价值/是否能恰好装满/方案数。
# 核心：内层循环从大到小（防止同一物品被重复选取）
for n in ns:
for i in range(T, n - 1, -1):
dp[i] = max(dp[i], dp[i - n] + ws[i])完全背包（每个物品可以选无限次，无序）
识别特征：与 0-1 背包类似，但每个物品可以重复使用。
# 核心：内层循环从小到大（允许同一物品被多次选取）
for n in ns:
for i in range(n, T + 1):
dp[i] = max(dp[i], dp[i - n] + ws[i])完全背包（有序，求排列数）
识别特征：求不同排列的方案数（顺序不同算不同方案）。
# 核心：外层循环遍历容量，内层循环遍历物品
for i in range(1, T + 1):
for n in ns:
dp[i] += dp[i - n]不同问题变体的转移方式：
# True/False 问题（能否恰好装满）
dp[i] |= dp[i - num]
# 最大/最小问题
dp[i] = min(dp[i], dp[i - num] + 1)
dp[i] = max(dp[i], dp[i - num] + 1)
# 方案计数
dp[i] += dp[i - num]相关力扣题：377 组合总和IV、494 目标和、518 零钱兑换II、139 单词拆分、416 分割等和子集、474 一和零、322 零钱兑换。
2.2 单串 DP
识别特征：一个数组/序列，
dp[i]代表以第 i 个元素结尾（或前 i 个元素）的某种最优值。
# 依赖前一个元素（如爬楼梯）
dp[i] = dp[i - 1] + ns[i]
# 依赖前面所有元素（如最长上升子序列）
for i in range(n):
for j in range(i):
dp[i] = min(dp[i], f(dp[j]))相关力扣题：70 爬楼梯、746 最小花费爬楼梯、300 最长上升子序列、801 使序列递增的最小交换次数。
2.3 双串 DP（LCS 最长公共子序列）
识别特征：两个字符串/序列，求它们的最长公共部分、编辑距离等。
dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
for j in range(M):
if t1[i] == t2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])2.4 区间 DP
识别特征：求一个区间
[i, j]上的最优值，且大区间依赖小区间的结果。常见于回文串、矩阵链乘。
# dp[i][j] 代表区间 [i, j] 的最优值
# 枚举顺序：i 从大到小，j 从小到大（保证小区间先计算）
dp = [[0] * N for _ in range(N)]
for j in range(N):
dp[j][j] = 1 # 单个元素的初始值
for i in range(j - 1, -1, -1):
if ss[i] == ss[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])相关力扣题：5 最长回文子串、647 回文子串、516 最长回文子序列、1312 最少插入次数变回文。
2.5 区间分治 DP
识别特征：区间 DP 的进阶版，需要在区间内枚举分割点 k。常见于戳气球、奇怪的打印机。
dp = [[0] * N for _ in range(N + 1)]
for l in range(N): # 区间长度从小到大
for i in range(N - l): # 以 i 为起点
j = i + l # 以 j 为终点
for k in range(i, j): # 以 k 为分割点
pass # 业务逻辑相关力扣题：312 戳气球、664 奇怪的打印机、486 预测赢家。
2.6 卡特兰数
识别特征：方案数符合递推关系
g(n) = sum(g(i) * g(n-1-i))。如不同BST的个数、合法括号序列个数。
dp = [1] + [0] * n
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]三、回溯算法模板
识别特征：题目要求列举所有方案/所有路径/所有排列/所有组合，或者问题规模较小（n <= 20 左右）。回溯的时间复杂度通常是 O(2^n) 或 O(n!)，本质是暴力穷举 + 剪枝。
3.1 通用框架
@functools.lru_cache(None) # 可选的记忆化剪枝
def backtrack(路径, 选择列表):
if 满足结束条件:
结果.append(路径)
return
for 选择 in 选择列表:
if visited[i]: # 剪枝
continue
做出选择
backtrack(新路径, 新选择列表)
撤销选择3.2 全排列（剪枝法）
力扣 46 全排列、47 全排列II
def backtrack(temp_list, length):
if length == n:
res.append(temp_list)
for i in range(n):
if not visited[i]:
visited[i] = 1
backtrack(temp_list + [nums[i]], length + 1)
visited[i] = 03.3 子集/组合（索引遍历法）
力扣 78 子集、90 子集II、131 分割字符串、39/40/216 组合系列
def helper(idx, n, temp_list):
if temp_list not in res:
res.append(temp_list)
for i in range(idx, n):
helper(i + 1, n, temp_list + [nums[i]])3.4 括号生成（资源消耗法）
力扣 22 括号生成
def backtrack(S, L, R):
if not L and not R:
ans.append(''.join(S))
return
if L: backtrack(S + ['('], L - 1, R)
if R > L: backtrack(S + [')'], L, R - 1)3.5 复原 IP 地址
力扣 93
def backtrack(i, tmp, flag):
if i == n and flag == 0:
res.append(tmp[:-1])
elif i < n and s[i] == '0':
backtrack(i + 1, tmp + s[i] + ".", flag - 1)
elif flag:
for j in range(i, min(n, i + 3)):
if 0 < int(s[i:j + 1]) <= 255:
backtrack(j + 1, tmp + s[i:j + 1] + ".", flag - 1)3.6 全排列（remains 版）与电话号码
# 全排列（不用 visited 数组的写法）
def dfs(path, remains):
if not remains:
res.append(path[:])
return
for i in range(len(remains)):
dfs(path + [remains[i]], remains[:i] + remains[i + 1:])
# 力扣 17 电话号码的字母组合
def dfs(pth, idx):
if idx == len(ds):
res.append(pth)
return
for c in dic[ds[idx]]:
dfs(pth + c, idx + 1)3.7 解数独 / N 皇后（多重约束）
力扣 37 解数独、51 N 皇后
def backtrack(pos):
if pos == n:
return True
i, j = empty[pos]
for num in row[i] & col[j] & block[bidx(i, j)]:
row[i].remove(num)
col[j].remove(num)
block[bidx(i, j)].remove(num)
board[i][j] = str(num)
if backtrack(pos + 1):
return True
row[i].add(num)
col[j].add(num)
block[bidx(i, j)].add(num)3.8 正则匹配（递归法）
力扣 10
def isMatch(self, s: str, p: str) -> bool:
if not p:
return not s
f = bool(s and p[0] in {s[0], '.'})
if len(p) >= 2 and p[1] == "*":
return self.isMatch(s, p[2:]) or f and self.isMatch(s[1:], p)
else:
return f and self.isMatch(s[1:], p[1:])四、并查集模板
识别特征：题目涉及"连通性"——判断两个元素是否属于同一组、合并两个组、统计连通分量个数。常见关键词：朋友圈、岛屿数量、冗余连接、等式方程。
dummy 虚拟节点用于连接具有某种特征的全部节点，类似链表的 preHead。
parent = {}
size = collections.defaultdict(lambda: 1)
cnt = 0
def find(x):
"""查找 x 的根节点，带路径压缩"""
parent.setdefault(x, x)
while x != parent[x]:
parent[x] = parent[parent[x]] # 路径压缩（隔代压缩）
x = parent[x]
return x
def union(x, y):
"""合并 x 和 y 所在的集合，按大小合并"""
nonlocal cnt
if connected(x, y):
return
xP, yP = find(x), find(y)
# 小树挂到大树上，保持平衡
if size[xP] < size[yP]:
parent[xP] = yP
else:
parent[yP] = xP
size[xP] += size[yP]
cnt -= 1
return size[xP]
def connected(x, y):
"""判断 x 和 y 是否在同一集合"""
return find(x) == find(y)
def add(x):
"""添加新元素"""
if x not in parent:
parent[x] = x
cnt += 1常见用法：
# 检查是否有环（无向图）
for a, b in edges:
if connected(a, b):
return True # a 和 b 已经连通，再加边就成环了
union(a, b)
# 将每个集合的元素按根节点分组
res = collections.defaultdict(list)
for e in elements:
res[find(e)].append(e)五、单调栈 / 单调队列模板
识别特征：需要找每个元素左边/右边第一个比它大（或小）的元素。常见关键词：下一个更大元素、每日温度、最大矩形、接雨水。
栈中一般存的是索引而非值。
5.1 通用单调栈
stack = []
for i in range(len(ns)):
while stack and ns[stack[-1]] <= ns[i]: # 单调递减栈
stack.pop()
# 此时 stack[-1] 是左边第一个比 ns[i] 大的元素的索引
stack.append(i)5.2 最大矩形（单调递增栈）
力扣 84 柱状图中最大的矩形
for i in range(len(hs)):
while s and hs[i] < hs[s[-1]]:
base = s.pop()
if s:
H = hs[base]
W = i - s[-1] - 1 # 当前弹出的做高，当前 i 与次小做宽
res = max(res, H * W)
s.append(i)5.3 去除重复字符（单调递增 + 考虑剩余）
力扣 316
for i, c in enumerate(ss):
if c not in s:
while s and c < s[-1] and s[-1] in ss[i:]:
s.pop()
s.append(c)5.4 接雨水（单调递减栈）
力扣 42
for i in range(len(hgt)):
while stack and hgt[i] > hgt[stack[-1]]:
base = stack.pop()
if stack:
LH = hgt[stack[-1]]
W = i - stack[-1] - 1
H = min(LH, hgt[i]) - hgt[base]
res += W * H
stack.append(i)5.5 每日温度（单调递减栈，反向遍历）
力扣 739
for i in range(len(T) - 1, -1, -1):
while s and T[s[-1]] <= T[i]:
s.pop()
res[i] = s[-1] - i if s else 0
s.append(i)六、二分查找模板
识别特征：有序数组中查找、答案具有单调性（满足某个条件的最小/最大值）、旋转排序数组。
6.1 bisect 语义说明
# 数组 1355579，T=5
# bisect_left => 返回 2（第一个 5 的位置）
# bisect_right => 返回 5（最后一个 5 的下一个位置）6.2 中位返回（标准二分）
力扣 33 搜索旋转排序数组、374 猜数字大小、69 x 的平方根
while L <= R:
M = (L + R) // 2
if nums[M] == T:
return M
elif nums[M] < T:
L = M + 1
else:
R = M - 16.3 区域压缩（找边界）
力扣 278 第一个错误版本、162 寻找峰值、153 寻找数组最小值
while L < R:
M = (L + R) // 2
if condition(M): # 满足条件，答案在左半边（含 M）
R = M
else: # 不满足，答案在右半边
L = M + 1七、滑动窗口模板
识别特征：在字符串/数组中找满足某个条件的最长/最短连续子串/子数组。常见关键词：最小覆盖子串、无重复字符的最长子串、字母异位词。
7.1 可变窗口（通用框架）
nd = collections.Counter(t) # 需要的字符及其个数
wd = {} # 窗口中的字符计数
L, R = 0, 0
cnt = 0 # 满足条件的字符个数
while R < len(s):
c = s[R] # 即将加入窗口的字符
R += 1
# 更新窗口数据（wd、cnt 等）
while 满足窗口收缩条件:
# 记录或更新结果
d = s[L] # 即将移出窗口的字符
L += 1
# 更新窗口数据
return 结果7.2 固定窗口
i = j = cnt = 0
for j in range(len(A)):
if A[j] == 0:
cnt += 1
if cnt > K: # 不满足时整体平移
if A[i] == 0:
cnt -= 1
i += 1
return j - i + 17.3 可变窗口（求最长）
for j in range(len(A)):
if A[j] == 0:
cnt += 1
while cnt > K: # 不满足时收缩左边界
if A[i] == 0:
cnt -= 1
i += 1
res = max(res, j - i + 1)
return res八、前缀和模板
识别特征：需要快速求任意子数组的和，或者统计满足某种和条件的子数组个数。常见关键词：子数组和为 K、最长子数组和为 K、连续子数组和被 K 整除。
8.1 累加和存位置（求最长子数组）
力扣 1371、525、325
psd = {0: -1} # 前缀和 -> 第一次出现的索引
for i in range(len(s)):
t ^= cd.get(s[i], 0) # 根据题意更新前缀和
if t not in psd:
psd[t] = i # 第一次出现，记录位置
else:
ans = max(ans, i - psd[t]) # 已出现过，计算长度8.2 累加和存数量（求子数组个数）
力扣 560 和为 K 的子数组数量
psd = {0: 1} # 前缀和 -> 出现次数
s = 0
for i in range(len(ns)):
s += ns[i]
if s - T in psd:
ans += psd[s - T]
psd[s] = psd.get(s, 0) + 18.3 模 K 前缀和
力扣 523（存索引）、974（存数量）
psd = {0: -1}
s = 0
for i in range(len(ns)):
s += ns[i]
if T != 0:
s %= abs(T) # 对 K 取模
if s not in psd:
psd[s] = i
elif i - psd[s] > 1:
return True8.4 矩阵前缀和
力扣 363、1074
for i in range(m): # 固定左边界
ps = [0] * n
for j in range(i, m): # 固定右边界
psS = 0
dct = {0: 1}
for k in range(n): # 以高做前缀和
ps[k] += mtx[j][k]
psS += ps[k]
cnt += dct.get(psS - T, 0)
dct[psS] = dct.get(psS, 0) + 1
return cnt九、拓扑排序模板
识别特征：有向无环图（DAG）中求一个合法的线性排列，或者判断图中是否有环。常见场景：课程表、编译依赖。
ins = [0] * n # 入度数组
ous = collections.defaultdict(list) # 邻接表（出度）
for cur, pre in prerequisites:
ins[cur] += 1
ous[pre].append(cur)
# 所有入度为 0 的节点入队
res = list(filter(lambda x: ins[x] == 0, range(n)))
q = collections.deque(res)
while q:
pre = q.popleft()
for cur in ous[pre]:
ins[cur] -= 1
if not ins[cur]: # 入度变为 0，解锁
q.append(cur)
res.append(cur)
# len(res) == n 说明无环，否则有环十、双指针模板
识别特征：在有序数组/链表中需要找满足某种条件的一对/一组元素，或者原地移除/去重/合并。
# 快慢指针：移除元素
def removeElement(ns, val):
slow = 0
for fast in range(len(ns)):
if ns[fast] != val:
ns[slow] = ns[fast]
slow += 1
return slow十一、深度优先（二叉树遍历模板大全）
识别特征：二叉树相关的几乎所有问题都可以用 DFS 解决。以下模板覆盖递归、迭代、标记法、莫里斯遍历、N 叉树遍历。
11.1 递归（最简洁）
def preOrd(root):
if not root:
return []
return [root.val] + preOrd(root.left) + preOrd(root.right)
# 中序：preOrd(root.left) + [root.val] + preOrd(root.right)
# 后序：preOrd(root.left) + preOrd(root.right) + [root.val]11.2 递归（通用模板，可扩展参数和返回条件）
def dfs(cur):
if not cur:
return
res.append(cur.val) # 前序位置
dfs(cur.left)
# res.append(cur.val) # 中序位置
dfs(cur.right)
# res.append(cur.val) # 后序位置11.3 迭代：前序（最常用）
if not root:
return []
res = []
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
# 后序：改为先左后右入栈，最后 res[::-1]11.4 迭代：中序（指针 + 栈）
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res11.5 迭代：标记法（前中后序通用）
通过 (flag, node) 标记节点是否已访问。只需调整入栈顺序即可切换前/中/后序。
res = []
stack = [(0, root)]
while stack:
flag, cur = stack.pop()
if not cur:
continue
if flag == 0:
# 前序：右、左、当前（倒序入栈）
stack.append((0, cur.right))
stack.append((0, cur.left))
stack.append((1, cur))
# 中序：右、当前、左
# 后序：当前、右、左
else:
res.append(cur.val)
return res11.6 层序遍历
from collections import deque
if not root:
return []
q = deque([root])
res = []
while q:
level = []
for _ in range(len(q)):
t = q.popleft()
level.append(t.val)
if t.left: q.append(t.left)
if t.right: q.append(t.right)
res.append(level)
return res11.7 莫里斯遍历（O(1) 空间）
利用线索二叉树的思想，将空指针指向中序后继/前驱，实现不用栈的遍历。
cur = root
while cur:
if not cur.left:
res.append(cur.val) # 访问（中序位置）
cur = cur.right
else:
pre = cur.left
while pre.right and pre.right != cur:
pre = pre.right
if not pre.right:
# 前序位置: res.append(cur.val)
pre.right = cur # 建立线索
cur = cur.left
else:
pre.right = None # 恢复树结构
res.append(cur.val) # 访问（中序位置）
cur = cur.right
return res11.8 N 叉树遍历
# 递归
def preorder(root):
if not root:
return []
res = [root.val]
for node in root.children:
res.extend(preorder(node))
return res
# 迭代
def preorder(root):
if not root:
return []
s = [root]
res = []
while s:
node = s.pop()
res.append(node.val)
s.extend(node.children[::-1])
return res十二、广度优先
识别特征：求最短路径（无权图）、逐层处理、从多个起点同时扩展。
12.1 无向图 BFS
q = collections.deque([start])
visited[start] = True
while q:
cur = q.popleft()
for nxt in graph[cur]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)12.2 二叉树层序遍历
见上方 11.6。
十三、图论算法
识别特征：有权图的最短路径、任意两点距离。
13.1 Dijkstra（单源最短路径）
适用于边权非负的有权图。
dic = collections.defaultdict(list)
for u, v, w in edges:
dic[u].append([v, w])
dic[v].append([u, w])
q = [(0, start)] # (距离, 节点)
dist = [-1] * (n + 1)
while q:
dis, cur = heapq.heappop(q)
if dist[cur] < 0: # 未访问
dist[cur] = dis
for nxt, wi in dic[cur]:
heapq.heappush(q, [dis + wi, nxt])13.2 Floyd（任意两点最短路径）
适用于需要求所有点对之间距离的场景，O(V^3)。
ds = defaultdict(int)
st = set()
for i, (x, y) in enumerate(edges):
ds[(x, y)] = vals[i]
ds[(y, x)] = 1 / vals[i]
st.update({x, y})
arr = list(st)
for k in arr: # 中间节点
for i in arr: # 起点
for j in arr: # 终点
if ds[(i, k)] and ds[(k, j)]:
ds[(i, j)] = ds[(i, k)] * ds[(k, j)]小结：如何用好这份模板手册
这份手册的正确用法不是"背下来"，而是建立题目特征 -> 模板的条件反射：
| 题目特征 | 应选模板 |
|---|---|
| 求最优值/方案数，子问题重叠 | 动态规划 |
| 列举所有方案/排列/组合 | 回溯 |
| 连通性/分组/判环 | 并查集 |
| 有向无环图线性排列 | 拓扑排序 |
| 下一个更大/更小元素 | 单调栈 |
| 有序数组查找/答案单调性 | 二分查找 |
| 最长/最短连续子串 | 滑动窗口 |
| 子数组和/前缀状态 | 前缀和 |
| 最短路径（无权图） | BFS |
| 最短路径（有权图） | Dijkstra |
| 二叉树 | DFS（递归/迭代） |
刷题时的建议流程：
- 读题 -> 识别特征：用上面的表格快速定位模板
- 套模板 -> 填业务逻辑：模板给你骨架，你负责填
dp[i]的定义、回溯的选择列表、滑窗的收缩条件 - 验证 -> 调试边界：大多数 bug 出在初始值和边界条件上
最后一点：模板是起点，不是终点。随着做题量的积累，你会发现很多题是多个模板的组合（比如"二分 + 前缀和""BFS + 并查集"），这时候模板的价值在于让你快速搭好骨架，把精力集中在真正需要思考的业务逻辑上。