LeetCode 核心题型分类与解题模式速查手册

Posted on Edited on In

数据结构

1. 序列、子序列与子数组 (核心模式归类)

A. 子数组 (Subarray - 连续性)

B. 子串 (Substring - 连续性)

C. 子序列 (Subsequence - 相对顺序)

2. 数组与矩阵 (核心模式归类)

A. 原地修改 / 数组作为哈希表 (实现 $O(1)$ 额外空间)

B. 矩阵遍历与坐标变换

  • 54. 螺旋矩阵【模式：四边界收缩；$(u, d, l, r)$ 指针随遍历向内挤压】
  • 36. 有效的数独【模式：一维化索引；利用 (r/3)*3 + c/3 映射九宫格】
  • 189. 轮转数组【模式：三次翻转；通过 reverse 实现 $O(1)$ 空间位移】
  • 31. 下一个排列【模式：标准算法；找 pivot -> 找更大数 -> 交换并反转】

C. 双指针、贪心与接雨水 (处理单调性或边界)

  • 11. 盛最多水的容器【模式：对撞指针；每次移动较短边以求更大容积】
  • 42. 接雨水【模式：双指针/单调栈；核心是“木桶原理”，高度由短板决定】
  • 407. 接雨水 II【模式：BFS + 优先队列；从外向内收缩 3D 边界】
  • 283. 移动零【模式：快慢指针；一个负责遍历，一个负责存放非零值】
  • 228. 汇总区间【模式：分组循环 / 双指针；核心：通过 nums[j+1] != nums[j]+1 识别连续区间断点】
  • 134. 加油站【模式：贪心；记录总收益与局部余量判断起点】
  • 135. 分发糖果【模式：双向遍历；确保同时满足左右邻居约束】

D. 前缀和与子数组 (处理区间和/积)

E. 区间处理 (排序 + 贪心)

  • 56. 合并区间【模式：区间合并；核心：按起点排序，维护 [L, R]，利用 l <= cur_right 动态扩展右边界】
  • 57. 插入区间【模式：分类讨论；核心：将区间分为“左侧不重叠”、“中间重叠合并”、“右侧不重叠”三部分处理】
  • 452. 用最少数量的箭引爆气球【模式：区间交集；核心：按终点排序，贪心选择重叠区域的边缘】
  • 435. 无重叠区间【模式：贪心留空；核心：按终点排序，尽量保留先结束的区间，以给后续留出更多空间】
  • 646. 最长数对链【模式：贪心；核心：按第二个数排序，贪心选择结束最早的区间，同 435 题】
  • 253. 会议室 II【模式：上下车/差分思想；核心：将起点看作 +1，终点看作 -1，求最大并发数；或利用小顶堆维护当前结束时间】
  • 228. 汇总区间【模式：分组循环 / 双指针；核心：识别连续数字序列的断点】
  • 2580. 统计将重叠区间合并成组的方案数【模式：区间合并 + 组合数学；核心：合并后得到 m 个独立连通块，结果为 $2^m$】

F. 查找、排序与二分

G. 哈希计数与频率统计 (利用数组或 Map 记录状态)

  • 1. 两数之和【模式：在线哈希查找；核心：在一次遍历中同时进行“查找”与“存入”，实现 $O(n)$ 时间复杂度】
  • 128. 最长连续序列【模式：哈希集合 + 智能起点；核心：利用 unordered_set 实现 $O(1)$ 查找，仅从序列起点 (x-1 不存在) 开始计数，确保 $O(n)$ 复杂度】
  • 217. 存在重复元素【模式：哈希集合；核心：利用 unordered_set 实现 $O(n)$ 频率检测，最基础的去重思想】
  • 219. 存在重复元素 II【模式：固定窗口哈希；核心：维护大小为 k 的 unordered_set】
  • 220. 存在重复元素 III【模式：滑动窗口 + 有序集合；核心：利用 std::set::lower_bound 寻找满足范围条件的元素】
  • 202. 快乐数【模式：循环检测；核心：利用 unordered_set 记录历史值或使用“快慢指针”在 $O(1)$ 空间内检测无限循环】
  • 383. 赎金信【模式：字符计数；利用 int[26] 数组实现 $O(n)$ 时间 $O(1)$ 空间的高性能频率校验】
  • 242. 有效的字母异位词【模式：频率对比；核心：利用 int[26] 计数，通过“先加后减”配合“负数早期退出”实现 $O(n)$ 校验】
  • 49. 字母异位词分组【模式：等类规约；核心：利用“排序后的字符串”或“字符频次”作为 Map 的 Key 进行归一化分类】
  • 387. 字符串中的第一个唯一字符【模式：两次遍历；先统计频次，再找第一个频次为 1 的索引】
  • 205. 同构字符串【模式：索引映射；通过 mapS[s[i]] == mapT[t[i]] 校验字符映射的一致性】
  • 290. 单词规律【模式：双向哈希；核心：利用双 Map 或 Map+Set 建立 char 与 string 的双射关系，注意利用 stringstream 处理单词拆分】
  • 266. 判断一个字符串是否是回文排列【模式：奇偶计数；回文排列最多只能有一个字符出现奇数次】
  • 409. 最长回文串【模式：贪心构造；统计成对出现的字符，最后可选加一个奇数项作为中心】

H. 缺失/重复/只出现一次的数字 (标记为负数/原地置换/位运算)

3. 栈与单调栈 (核心模式归类)

A. 基础栈应用与模拟 (处理嵌套、撤销与状态存取)

  • 20. 有效的括号【模式：括号匹配；核心：利用栈的 LIFO 特性处理嵌套关系】
  • 150. 逆波兰表达式求值【模式：后缀表达式计算；核心：遇到运算符弹出两数计算，注意减/除顺序】
  • 224. 基本计算器【模式：符号栈模拟；核心：利用栈维护当前括号层级的“全局正负号”，实现 $O(n)$ 一次遍历展开括号】
  • 155. 最小栈【模式：双栈/辅助栈；核心：同步维护一个“当前的最小值”栈】
  • 232. 用栈实现队列【模式：双栈翻转；核心：利用入栈和出栈两个容器实现 FIFO】
  • 394. 字符串解码【模式：多栈状态存取；核心：分别用栈存储当前的倍数 cnt 和已拼出的 string】
  • 71. 简化路径【模式：路径模拟；核心：遇到 .. 执行出栈，配合 stringstream 拆分单词】

B. 单调栈基础 (在线性时间内寻找左右最近的极值)

C. 单调栈进阶 (处理区间面积与贡献度计算)

  • 84. 柱状图中最大的矩形【模式：左右扩展边界；核心：利用单调栈一次性确定每个柱子的左、右边界，求最大矩形面积】
  • 907. 子数组的最小值之和【模式：贡献度法；核心：计算每个元素作为最小值的区间覆盖范围 $(i-L)*(R-i)$】
  • 2866. 美丽塔 II【模式：前后缀单调栈；核心：分别计算左侧和右侧的单调递增和，最后枚举顶点取 Max】
  • 768. 最多能完成排序的块 II【模式：单调栈维护块极值；核心：栈中每个元素代表一个“块”的最大值，重叠则合并】

D. 栈与贪心/其他

3. 队列与双端队列 (Queue & Deque)

4. 优先队列与堆 (Priority Queue & Heap)

A. 基础堆应用 (Top K / 动态极值 / 中位数)

B. 反悔贪心 (Regret Greedy - 核心模式)

  • 630. 课程表 III【模式：大顶堆维护耗时；遇到冲突时“反悔”替换掉耗时最长的课程】
  • LCP 30. 魔塔游戏【模式：小顶堆维护负值；血量不足时“反悔”将之前扣血最多的移到最后】
  • 871. 最低加油次数【模式：大顶堆维护油量；油不够时“反悔”在之前经过的油量最大的站加油】
  • 502. IPO【模式：双堆；按资本排序 + 大顶堆选利润最大的项目】

C. 最短路径与图搜索 (Dijkstra 及其变体)

D. 区间与会议室 (扫描线 / 堆优化)

  • 253. 会议室 II【模式：小顶堆；堆顶存储最早结束的会议时间，判断是否需开新房】

5. 链表 (核心模式归类)

A. 基础操作与反转 (双指针、递归与 Dummy Node)

B. 快慢指针与环形检测

  • 141. 环形链表【模式：快慢指针；核心：利用步长差 $(2-1=1)$，在 $O(n)$ 时间 $O(1)$ 空间内检测链表是否有环】
  • 142. 环形链表 II【模式：双指针追赶；核心：相遇后将一指针归零，同步慢走寻找环入口】
  • 19. 删除链表的倒数第 N 个结点【模式：快慢指针；核心：利用 $n$ 步位移差定位倒数第 $n+1$ 个节点（前驱节点）】
  • 61. 旋转链表【模式：成环解环；核心：先连成环再在 $n-(k%n)$ 处断开，简化指针操作】
  • 876. 链表的中间结点【模式：快慢指针；核心：fast 走两步 slow 走一步，fast 到头时 slow 在中点】
  • 287. 寻找重复数【模式：映射找环；将数组索引视为链表指针，转化为环入口问题】

C. 合并、排序与分隔

D. 复杂链表与采样

  • 138. 随机链表的复制【模式：原地克隆；核心：A->A'->B->B' 插入法，实现 $O(1)$ 空间拷贝随机指针】
  • 382. 链表随机节点【模式：水塘抽样；核心：从未知长度流中等概率采样，确保概率为 $1/i$】
  • 146. LRU 缓存【模式：哈希表 + 双向链表；实现 $O(1)$ 的访问与淘汰】
  • 460. LFU 缓存【模式：双哈希表 + 频次链表；实现 $O(1)$ 的频率敏感淘汰】

6. 二叉树与树形结构 (核心模式归类)

A. 遍历、属性与结构基础 (递归与迭代)

B. 路径、祖先与贡献度计算 (DFS 进阶)

C. 构造、变换与序列化

D. 二叉搜索树 (BST 专项)

7. 树与图论 (Tree & Graph - 核心模式归类)

A. 树的基础与进阶 (Tree)

B. 网格搜索与连通性 (DFS/BFS)

  • 200. 岛屿数量【模式：DFS/BFS；核心：原地修改标记（沉岛）实现 $O(1)$ 空间】
  • 305. 岛屿数量 II【模式：并查集 (Union-Find)；核心：动态维护连通分量，将”陆地化”转化为”集合合并”】
  • 130. 被围绕的区域【模式：逆向思维；从边界 'O' 开始标记，未被标记的内部 'O' 均需填充】
  • 133. 克隆图【模式：哈希表 + DFS/BFS；核心：利用 Map 存储 [原节点 -> 新节点] 防止死循环】
  • 399. 除法求值【模式：带权图搜索；将变量视为节点，比值视为边权，通过 DFS 或并查集求解】

C. 拓扑排序 (有向无环图 DAG)

D. 广度优先搜索进阶 (最短路径/步数)

  • 909. 蛇梯棋【模式：BFS；核心：一维坐标与二维矩阵的映射转换】
  • 433. 最小基因变化【模式：单向/双向 BFS；寻找状态空间的最短路径】
  • 127. 单词接龙【模式：双向 BFS；核心：利用中间态（如 h*t）优化状态转移搜索】

E. 最短路径算法 (Dijkstra/Floyd/Bellman)

F. 高级图论与连通性 (并查集/基环树/网络流)

8. 平衡二叉搜索树 (std::map/set)

9. 区间查询与更新 (Range Query & Update)

核心思想：高效处理区间操作的数据结构家族。从静态的前缀和到动态的线段树，根据问题的查询/更新需求选择合适的工具。

技术演进路径：前缀和（静态查询）→ 差分（批量更新）→ 树状数组（动态单点）→ 线段树（动态区间）

A. 前缀和与后缀和 (Prefix Sum & Suffix Sum)

场景：静态数组的快速区间查询；预处理 $O(n)$，查询 $O(1)$
核心：sum[l, r] = prefix[r+1] - prefix[l]，支持一维/二维/前缀积等变体

B. 差分数组 (Difference Array)

场景：多次区间更新 + 一次性查询；时间 $O(n + q)$，空间 $O(n)$
核心：diff[l] += val, diff[r+1] -= val，最后前缀和还原；是前缀和的”逆运算”

C. 树状数组 (Binary Indexed Tree / Fenwick Tree)

场景：单点更新 + 区间查询（前缀和）；时间 $O(\log n)$，空间 $O(n)$
核心：利用 lowbit(x) = x & -x 实现树状结构，是动态版本的前缀和

D. 线段树 (Segment Tree)

场景：区间更新 + 区间查询（最大/最小/和）；时间 $O(\log n)$，空间 $O(n)$ 或动态开点
核心：完全二叉树结构，支持懒标记（Lazy Propagation）批量更新，是最通用的区间数据结构

11. 字典树 (Trie)

12. 并查集 (Union Find)

13. 数据结构设计与实现 (Consolidated)

A. 基础结构实现

B. 缓存与高级哈希

C. 树与图的高级结构

14. 离线query

15. 回文串 (Palindrome)

基本算法

18. 双指针 (Two Pointers)

核心：关注两个“点”的博弈，利用有序性或特征缩减搜索空间。

A. 对撞指针 (相向移动)

场景：有序数组求和、反转、容积问题

B. 快慢指针 (同向移动)

场景：原地修改、子序列匹配、区间归并

19. 滑动窗口 (Sliding Window)

核心：关注两个指针中间的“区域/区间”的性质维护。

A. 不定长窗口：求最长/最大 (Variable Length - Max)

逻辑：Right 扩张 -> 满足条件? -> 更新结果

B. 不定长窗口：求最短/最小 (Variable Length - Min)

逻辑：Right 扩张 -> 满足条件? -> Left 收缩 (Update Min) -> 循环直到不满足

C. 固定窗口 (Fixed Length)

逻辑：窗口大小固定为 K，Right 进 Left 出

D. 窗口内的特殊统计 (结合其他数据结构)

21. Top K / 中位数 / 第 K 小元素 (Top K & Selection Problems)

核心思想：从海量数据中高效选取第 K 个元素或维护动态极值，是算法面试的高频考点。

A. 快速选择与堆 (QuickSelect & Heap)

场景：无序数组中找第 K 大/小元素

B. 对顶堆与数据流 (Dual Heap & Stream)

场景：动态数据流中维护中位数或极值

  • 295. 数据流的中位数【模式：对顶堆；核心：最大堆维护左半部（较小值），最小堆维护右半部（较大值），保持两堆大小平衡】
  • 480. 滑动窗口中位数【模式：对顶堆 + 延迟删除；核心：在滑动窗口场景下维护动态中位数】

C. 二分答案与有序结构 (Binary Search & Sorted Structure)

场景：有序矩阵、多数组归并中的第 K 小问题

D. 多路归并与有序序列生成 (Multi-way Merge)

场景：从多个有序源中生成第 K 个元素

  • 面试题 17.09. 第 k 个数【模式：三指针 DP / 多路归并；核心：维护 p3, p5, p7 三个指针，每次选择 min(dp[p3]*3, dp[p5]*5, dp[p7]*7) 作为下一个魔法数，相等时多指针同时前移去重；最优 $O(k)$ 时间复杂度，类似 264 题丑数 II】
  • 264. 丑数 II【模式：三指针 DP / 小顶堆；核心：按序生成仅含质因子 2, 3, 5 的数字】
  • 23. 合并 K 个升序链表【模式：最小堆 / 分治归并；核心：维护 K 个链表头的最小值，或两两分治合并】

22. 排序算法与应用 (Sorting Algorithms & Applications)

核心思想：排序是算法的基础工具，通过消除无序性简化问题，常与双指针、贪心、二分等技巧结合。

A. 排序算法实现 (Algorithm Implementation)

场景：手撕排序算法、理解排序原理

  • 912. 排序数组【模式：快速排序 / 归并排序；核心：快排三段式 (less, equal, more)，归并分治合并】
  • 148. 排序链表【模式：链表归并排序；核心：快慢指针找中点 + 递归拆分 + 有序链表合并；注意：断开中点连接以防止死循环】
  • 147. 对链表进行插入排序【模式：插入排序；核心：维护已排序部分，将新节点插入合适位置】

B. 自定义排序 (Custom Comparator)

场景：需要特殊排序规则的问题

C. 有序数组/链表合并 (Merge Sorted Sequences)

场景：多个有序序列的合并

D. 排序 + 双指针 (Sorting + Two Pointers)

场景：排序后利用有序性进行双指针搜索

E. 排序 + 贪心 (Sorting + Greedy)

场景：排序后贪心选择、区间处理

F. 排序 + 枚举/分界线 (Sorting + Enumeration)

场景：排序后枚举关键点或分界线

场景：排序后利用单调性进行二分或 LIS

H. 排序块问题 (Chunk Sorting)

场景：判断数组能否分块排序

I. 有序结构与 BST (Sorted Structure)

场景：利用有序性质的特殊问题

J. 拓扑排序 (Topological Sort)

场景：有向无环图的线性排序

23. 字符串匹配 (KMP / AC 自动机)

24. 枚举

25. 模拟/分组/循环 (group/cycle arrray/模拟/易错)

26. 贪心算法 (Greedy Algorithm - 核心模式归类)

A. 基础贪心与排序 (利用排序消除维度影响)

B. 反悔贪心 (结合优先队列动态调整)

  • 630. 课程表 III【模式：反悔贪心；核心：先按截止时间排序，若当前无法加入则替换掉之前耗时最长的课程】
  • 502. IPO【模式：双堆/排序+大顶堆；核心：动态选择当前资金下利润最大的项目】
  • LCP 30. 魔塔游戏【模式：反悔贪心；核心：血量不足时将之前扣血最多的房间移到最后】
  • 871. 最低加油次数【模式：反悔贪心；核心：油不够时从经过的加油站中选油最多的加】

C. 贡献度法与数学贪心

D. 区间处理 (排序 + 边界维护)

E. 邻居约束与多遍遍历

F. 贪心 + 二分/DP 结合

27. 分治 (Divide and Conquer)

核心逻辑：

  1. **分解 (Divide)**：将原问题拆分为规模较小、相互独立的子问题（如左右子树、数组半区）。
  2. **解决 (Conquer)**：递归解决子问题，直到触及边界。
  3. **合并 (Combine)**：将子问题的解合并为原问题的解（如归并排序的 merge 或 LCA 的状态上传）。

28. 贡献法 (Contribution Method)

核心思想：不枚举所有可能的子集/子数组，而是枚举每个元素，计算该元素对最终答案的“贡献”次数或值。

A. 单调栈 + 贡献法 (区间极值贡献)

B. 数学/位运算/点对贡献

C. 树上贡献 (边/点贡献)

数学 (Mathematics - 核心模式归类)

28. 数论基础 (Number Theory)

A. 质数、约数与筛选法

B. 最大公约数 (GCD) 与 最小公倍数 (LCM)

C. 数字处理与投票算法

  • 9. 回文数【模式：数学反转；核心：反转一半数字与前半部分比较，避免溢出】
  • 169. 多数元素【模式：Boyer-Moore 摩尔投票法；$O(n)$ 时间 $O(1)$ 空间找众数】
  • 229. 多数元素 II【模式：进阶摩尔投票；统计出现次数超过 $n/3$ 的元素】
  • 400. 第 N 位数字【模式：数学模拟；按位数区间（个位、十位…）定位数字】
  • 343. 整数拆分【模式：数学推导；核心：尽可能拆分成 3 以获得最大乘积】

28. 组合数学与概率 (Combinatorics & Probability)

A. 排列组合与大数取模

B. 模运算与乘法逆元

C. 随机采样 (Sampling)

29. 位运算 (Bit Manipulation)

A. 基础技巧与 Lowbit

  • 核心性质：n & (n-1) 消除最低位 1；n & -n 获取最低位 1 (lowbit)】
  • 191. 位 1 的个数【模式：__builtin_popcount 或 n & (n-1) 迭代】
  • 190. 颠倒二进制位【模式：位操作；逐位反转 ans = (ans << 1) | (n & 1) 或 分治法】
  • 231. 2 的幂【模式：n > 0 && (n & (n-1)) == 0】
  • 201. 数字范围按位与【模式：公共前缀；寻找 left 和 right 的二进制公共前缀】

B. 异或 (XOR) 专项

30. 快速幂与几何 (Fast Power & Geometry)

搜索问题核心分类与总结 (Search Strategies)

31. DFS 与回溯：全量枚举与约束满足 (DFS & Backtracking)

核心区别：

  • DFS（深度优先搜索）：遍历所有状态，通常用于连通性判断、路径查找、拓扑排序
  • 回溯（Backtracking）：在 DFS 基础上增加”撤销选择”，用于求解组合优化问题（排列、组合、子集）

A. 基础 DFS：遍历与连通性 (Traversal & Connectivity)

场景：图/树的遍历、连通分量统计、环检测

  • 200. 岛屿数量【模式：连通分量统计；核心：DFS 标记连通区域，原地修改避免 visited 数组】
  • 133. 克隆图【模式：哈希表 + DFS；核心：用 Map 存储 [原节点 -> 新节点] 防止死循环】
  • 2101. 引爆最多的炸弹【模式：有向图 DFS；核心：枚举起点，DFS 统计可达节点数】

B. 树上 DFS：路径与状态聚合 (Tree DFS)

场景：路径和、路径记录、子树信息聚合

  • 112. 路径总和【模式：DFS 递归；核心：判断是否存在根到叶子路径和等于目标值，叶子节点定义为左右子树均为空】
  • 113. 路径总和 II【模式：回溯 + 路径记录；核心：DFS 遍历时维护 path 数组，到达叶子节点且路径和等于目标值时保存当前路径的副本，回溯时弹出节点】
  • 437. 路径总和 III【模式：前缀和 + 哈希表；核心：路径不必从根开始，利用 prefixSum - targetSum 统计满足条件的路径数，类似 560 题】
  • 2477. 到达首都的最少油耗【模式：后序 DFS / 树形 DP；核心：从根节点开始后序遍历，递归返回子树总人数，每个节点计算 ⌈人数/seats⌉ 辆车的油耗；也可用拓扑排序 BFS 从叶子向根逐层合并（见 BFS 章节）】

C. 回溯：组合与排列 (Backtracking - Combinations & Permutations)

场景：求所有方案、排列组合、子集生成

💡 回溯去重口诀
  • 组合靠 start：不回头看，一路向右。
  • 排列靠 used：全员参与，位掩码标记。
  • 重复靠排序：前人未用，后人莫入（!used[i-1]）。
  • 17. 电话号码的字母组合【模式：基础回溯；核心：递归深度控制数字索引，for 循环遍历字母映射】
  • 77. 组合【模式：组合回溯；核心：【口诀】组合靠 start：不回头看，一路向右】
  • 39. 组合总和【模式：重复选组合；核心：【原理】传递当前索引 i 而非 i+1 实现元素可重复选取】
  • 46. 全排列【模式：排列回溯；核心：【口诀】排列靠 used：全员参与，位掩码标记】
  • 47. 全排列 II【模式：有重排列；核心：【原理】重复靠排序：前人未用，后人莫入（!used[i-1]）】
  • LCR 086. 分割回文串【模式：子串划分；核心：枚举分割点，预处理回文表优化判断】

D. 回溯：约束满足问题 (Constraint Satisfaction Problems)

场景：棋盘问题、数独、复杂约束条件

💡 约束优化口诀
  • 棋盘靠标记：列号、和、差，三位一体定乾坤。
  • 括号看余额：左括号不超标，右括号不透支。
  • 矩阵靠沉岛：先占位再递归，事后记得还原。
  • 51. N 皇后【模式：棋盘回溯；核心：【口诀】棋盘靠标记：列号、和、差，三位一体定乾坤】
  • 52. N 皇后 II【模式：棋盘回溯；核心：利用 cols[c]、diag1[r+c]、diag2[r-c+n] 三个数组实现 O(1) 冲突检测】
  • 22. 括号生成【模式：配对回溯；核心：【口诀】括号看余额：左括号不超标，右括号不透支】
  • 79. 单词搜索【模式：矩阵回溯；核心：【口诀】矩阵靠沉岛：先占位再递归，事后记得还原】

E. 记忆化搜索 (Memoization DFS)

场景：重叠子问题、状态空间搜索、自顶向下 DP

DP 问题 (Dynamic Programming - 核心模式归类)

DP 类问题处理五部曲总结

步骤 核心任务 (Key Action) 你的代码体现 (Example) 空间优化思路 (Space Optimization)
1. 状态定义 明确 dp 数组各维度的物理含义（是长度、最值还是布尔值？对应什么区间？） dp[i][j] 表示到达坐标 (i,j) 的最小路径和 维度压缩：若当前状态只依赖前一状态，可将二维数组降为一维（或常数个变量）。
2. 转移方程 逻辑推导过程，包括不同条件下的决策 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 原地修改：如果输入数组（如 grid）后续不再使用，可以直接在原数组上操作实现 $O(1)$ 额外空间。
3. 初始边界 算法开始的基石（如单字符情况、空串情况），确定无需推导的“种子”值 初始化 dp[0][0]，并单独处理首行 dp[0][i] 和首列 dp[i][0] 虚拟边界：有时可以多申请一行/一列（如 dp[m+1][n+1]）并填入占位值，从而统一循环内的逻辑。
4. 计算顺序 确定循环的方向（Top-down vs Bottom-up），由状态依赖关系决定 使用双重 for 循环，从左到右、从上到下遍历 倒序遍历：在 0/1 背包等问题中，通过倒序遍历一维 DP 数组，可以防止当前层的计算污染待使用的旧数据。
5. 最终结果 确定答案在 dp 表中的存储位置 返回 dp[m-1][n-1] 状态追踪：如果不仅要结果还要路径，通常需要额外的 parent 数组记录来源，空间优化此时会受限。
6. 复杂度分析 分析时间与空间开销 时间 $O(M \times N)$，空间 $O(M \times N)$ 时空权衡：有时为了降低时间复杂度（如利用前缀和优化转移），可能会增加空间复杂度。

33. 状态转移流派：局部依赖 vs 全局扫描

核心逻辑：识别“依赖范围”是掌握 DP 的精髓。你可以把 DP 想象成“在过去中寻找最优解”。

维度 局部依赖型 (Local Dependency) 全局扫描型 (Global Scanning)
转移特征 dp[i] = f(dp[i-1], dp[i-2], ...) dp[i] = f(dp[0...i-1])
暴力复杂度 $O(n)$ $O(n^2)$
掌握重点 空间优化 (滚动数组/变量替代) 时间优化 (数据结构/二分/单调性)
一眼辨别 “我只能从前一个或前几个状态跳过来” “我可以从前面任意一个符合条件的点跳过来”

A. 第一流派：局部依赖 (局部记忆型)

核心特点：只需要知道“最近”的几步，就能决定下一步。如果发现 dp[i] 只依赖 dp[i-1]，通常可以压缩至 $O(1)$ 空间。

B. 第二流派：全局扫描 (区间/全历史扫描型)

核心特点：需要纵观所有历史状态才能决定下一步。面试常考“如何将 $O(n^2)$ 降到 $O(n \log n)$ 或 $O(n)$”。

  • 300. 最长递增子序列【模式：$dp[i] = max(dp[j]) + 1$，需遍历所有 $j < i$】
  • 139. 单词拆分【模式：需检查 $0$ 到 $i-1$ 所有可能的断点 $j$】
  • 85. 最大矩形【模式：需要结合单调栈进行全局扫描】
  • 区间 DP：如矩阵链乘法，需要遍历所有可能的切分点。

34. 基础线性 DP (1D/2D 填表)

最基础的递推，dp[i] 只依赖于前面几个状态

A. 斐波那契/爬楼梯模型

B. 网格路径模型 (Grid)

C. 简单一维推导

35. 状态机 DP (State Machine)

核心在于定义“持有”、“冷冻”、“卖出”等有限状态，画状态转移图

A. 股票系列

B. 其他状态机

C. 打家劫舍系列汇总 (House Robber)

36. 序列 DP (双串/单串)

处理字符串或数组子序列问题，核心是 LCS/LIS 模型

A. 单串 LIS 模型 ($O(n^2)$ 或 $O(n \log n)$)

B. 双串 LCS 模型 (二维表,m + 1,n + 1 处理空串的情况)

  • 1143. 最长公共子序列【模式：双串 DP；dp[i][j] = s1[i]==s2[j] ? dp[i-1][j-1]+1 : max(左, 上)；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 72. 编辑距离【模式：增删改三选一；dp[i][j] = min(插入, 删除, 替换) + 1；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 97. 交错字符串【模式：双串 DP；dp[i][j] 表示 s1[0..i] 和 s2[0..j] 能否交错组成 s3[0..i+j]；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 583. 两个字符串的删除操作【模式：LCS 变体；结果为 m + n - 2 * LCS；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 1035. 不相交的线【模式：LCS 本质；完全等同于最长公共子序列；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 115. 不同的子序列【模式：计数 DP；s[i]==t[j] 时可选匹配或不匹配，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]；注意：DP 数组大小为 (M+1)*(N+1) 处理空串】
  • 10. 正则表达式匹配【模式：双串 DP；核心：dp[i][j] 匹配 s[0..i] 和 p[0..j]；遇到 * 时可匹配 0 次或多次前字符；*注意：DP 数组大小为 (M+1)(N+1)**】
  • 44. 通配符匹配【模式：双串 DP；核心：* 可匹配任意序列；dp[i][j] = dp[i][j-1] || dp[i-1][j]】

C. 回文串模型

37. 划分型 DP (Partition)

将数组/字符串切分为 k 段，求最优解

37. 背包 DP (Knapsack)

组合优化问题，关注容量与价值

A. 0/1 背包

B. 完全背包

C. 多重/分组背包

38. 区间 DP (Interval)

从小区间合并到大区间，枚举分割点 k

39. 树形 DP (Tree DP)

自底向上汇总信息，或换根 DP

A. 子树贡献/直径

B. 换根 DP

40. 状压 DP (Bitmask)

数据范围 n < 20，用二进制表示集合

  • 464. 我能赢吗【模式：记忆化搜索 + 状压；核心：利用二进制 mask 记录数字使用状态，博弈论必胜态判断】
  • 526. 优美的排列【模式：状压 DP / 回溯；核心：dp[mask] 表示选取状态为 mask 时的方案数，或 DFS 剪枝】
  • 847. 访问所有节点的最短路径【模式：BFS + 状压；核心：状态定义为 (node, mask)，求覆盖所有节点的最短路】
  • 698. 划分为k个相等的子集【模式：状压 DP / 回溯；核心：dp[mask] 记录当前累加和，或 DFS 每次凑齐一个桶】
  • 2741. 特别的排列【模式：状压 DP；核心：dp[mask][last_val] 记录状态与上一个元素，满足整除关系转移】

41. 数位 DP (Digit DP)

按位填数，通常配合记忆化搜索

42. 其他/高级 DP

C++ 字符处理函数速查

函数名 检查内容 说明
isdigit(c) 是否为数字 (0-9) 数字字符
isalpha(c) 是否为字母 (a-z, A-Z) 纯字符/字母
isalnum(c) 是否为字母或数字 字母数字混合
tolower(c) 转换为小写 字符转换
toupper(c) 转换为大写 字符转换

参考