判断用哪个算法策略
1. 回溯法 = 试探、回退、找所有方案 / 可行解
典型题目：
- 8皇后
- 迷宫问题
- 子集、排列、组合
- 图的着色
- 寻找所有合法路径
关键词
所有解、能不能放、行不行、尝试、不行就退
一句话记忆
要“试来试去、退回重来” → 回溯！
2. 分治法 = 大问题切小问题，各自解决再合并
典型题目：
- 归并排序
- 快速排序
- 二分查找
- 最大子数组和（分治版）
关键词
拆成两半、互不影响、分别算、最后合并
一句话记忆
大事化小，小事化了，最后拼起来 → 分治！
3. 贪心法 = 每一步选当前最好，不回头
典型题目：
- 活动选择
- 哈夫曼编码
- 硬币找零（某些情况）
- 最短路径（Dijkstra 也算贪心思想）
- TSP 最近邻（近似解）
关键词
局部最优、眼前最好、直接选、不回头
一句话记忆
走一步看一步，只选眼前最好 → 贪心！
重点
贪心不一定得到全局最优！（如TSP）
4. 动态规划 DP = 最优解 + 子问题重复 + 记录表
典型题目：
- 01背包
- 最长公共子序列LCS
- 最短路径Floyd
- TSP（精确解）
- 矩阵链乘法
关键词
求最优（最小/最大/最短/最长）
子问题会重复
用表记住结果，避免重复算
一句话记忆
要最优、子问题重复、要查表 → DP！
5. 分支限界法 = 回溯/搜索 + 剪枝（求最优）
典型题目：
- TSP最优解
- 01背包最优解
关键词：
搜索所有可能，但发现不行就提前剪掉
一句话记忆：
边搜边剪，只为最优 → 分支限界！
最容易混淆的 4 组对比
1. 回溯 vs 动态规划
- 回溯：找所有可行解，不一定要最优
- 动态规划：一定要最优解，子问题重复
2. 贪心 vs 动态规划
- 贪心：只看眼前，不看未来
- 动态规划：看所有子问题，选全局最优
3. 分治 vs 动态规划
- 分治：子问题不重叠
- 动态规划：子问题重叠
4. 回溯 vs 分支限界
- 回溯：DFS，找所有解
- 分支限界：剪枝，只找最优
经典题直接对应
- 8皇后 → 回溯
- TSP（求所有路径/小数据）→ 回溯
- TSP（求最优）→ DP / 分支限界
- 归并排序/快排 → 分治
- 活动安排 → 贪心
- 01背包 → DP
- 迷宫 → 回溯
- 最短路径Dijkstra → 贪心
- 排列/组合/子集 → 回溯
这样问自己：
- 要找所有可行解？ → 回溯
- 要找最优解（最小/最大/最短）？
→ 子问题重复 → DP
→ 每步眼前最优就行 → 贪心 - 能切成两半独立算？ → 分治
- 搜索+剪枝求最优？ → 分支限界