LeetCode 解题思路总结

回溯

• 从答案角度：往 path 中添加元素。
• 从本层输入角度：做“选 / 不选”的分支。

动态规划

• 第一类：dp 最终位置就是问题答案。
• 递归定义通常就是原问题本身。
• 第二类：dp 最终位置不是直接答案，需要再做一次筛选（最大值、最小值等）。
• 递归定义通常是“某一类状态”而非原问题本身。
• 先穷举状态并分类，再加入最优属性；若“当前类最优值”依赖“其他类最优值”，该分类通常有效。

常见思路

• 先给可能答案分类，再分析各类之间关系，是非常实用的方法。
• 最大子数组和：按起点或终点分类都能得到递推关系。
• 乘积小于 k 的子数组：按右端点分类更自然。
• 递归的本质是抽取“本问题和子问题的同构模式”；差异部分放到参数或全局维护变量里。

如何判断题型

• 子数组 / 子串长度、替换次数、删除次数：优先考虑滑动窗口。
• 路径、组合、子集、分割：优先考虑回溯。
• 子数组、子序列的最值或计数：优先考虑动态规划。

零散规律

• 已知数据规模且要求第 K 大 / 第 K 小时，可优先考虑快速选择。
• 前缀和适合处理任意起点、任意长度的连续子数组和。
• 子数组 DP 中，“以 i 结尾”的状态至少包含 nums[i]。
• 子串统计中，长串出现次数不会超过其短前缀子串出现次数。