深入理解计算机科学中最基础且强大的三种算法思想
"一条路走到黑，不行就退回一步换条路"
尽可能深地探索当前分支，直到尽头后回溯到最近未探索节点继续深入
"层层推进，由近及远"
逐层探索：先访问所有相邻节点，再访问这些节点的相邻节点
"聪明的会计拆解复杂账单"
将问题分解为子问题，存储子问题的解，避免重复计算
| 特性 | DFS (深度优先搜索) | BFS (广度优先搜索) | DP (动态规划) |
|---|---|---|---|
| 核心策略 | 深度优先，回溯 | 广度优先，逐层推进 | 分解子问题，记忆化/制表，避免重复计算 |
| 数据结构 | 栈 (显式或隐式递归栈) | 队列 (Queue) | 数组/表 (存储状态值) |
| 空间复杂度 | O(h) 或 O(V) (树高 或 节点数) | O(w) 或 O(V) (树宽 或 节点数) | O(子问题数量) (通常是多项式级) |
| 时间复杂度 | O(V + E) | O(V + E) | 依赖于子问题数量和状态转移复杂度 |
| 解的性质 | 找到路径，不一定最短 (边数) | 总能找到最短路径 (边数，无权图) | 找到最优解 (最小值、最大值、可行性等) |
| 关键应用 | 连通性、拓扑排序、环检测、回溯、迷宫路径 | 无权图最短路径、连通性、层级遍历、广播 | 优化问题：背包、LCS、LIS、编辑距离、最短路径(带权)等 |
| 核心要求 | 图/树结构 | 图/树结构 | 最优子结构 + 重叠子问题 |
像一个勇敢但有点固执的探险家，在迷宫里遇到岔路时，总是选择一条路一直走下去，直到死胡同，然后退回到上一个岔路口选择另一条路。
像一个严谨的扫描仪，它站在起点，先探测所有一步就能到达的地方，然后探测所有两步能到达的地方，确保找到最短路径。
像一个聪明的会计在算一笔复杂账。他把大账单拆成很多小账单，并把每个小账单的结果都仔细记录下来，需要时直接查记录而不是重新计算。