动态规划（DP）思想
核心思想
将复杂问题分解为重叠子问题和最优子结构，通过存储子问题的解（状态）避免重复计算，从而高效求解。
- 重叠子问题：子问题反复出现（如斐波那契数列中计算
f(n)需多次计算f(n-1)、f(n-2)）。 - 最优子结构：问题的最优解包含子问题的最优解（如背包问题中，容量
w的最优解依赖于容量w-1、w-2等的最优解）。
关键要素
- 状态定义：用
dp[i]表示以i为结尾 / 边界的子问题的解。 - 状态转移方程：描述如何从更小的子问题推导出当前状态（核心难点）。
- 初始化：最小子问题的解（如
dp[0] = 0）。 - 遍历顺序：自底向上（迭代）或自顶向下（记忆化搜索）。
经典例子
- 背包问题：0-1 背包（每个物品选或不选，
dp[i][w]表示前i个物品、容量w时的最大价值）。 - 爬楼梯：
dp[n] = dp[n-1] + dp[n-2]，每次可以走 1 或 2 步。 - 最长公共子序列（LCS）：
dp[i][j]表示字符串A前i个字符和B前j个字符的 LCS 长度。
面试官常见问题
问题 1：DP 和分治算法的区别？
答：分治（如归并排序）将问题划分为互不重叠的子问题，子问题独立求解；DP 的子问题有重叠，需存储中间结果。分治侧重 “分而治之”，DP 侧重 “重复利用子问题解”。
问题 2：如何设计状态转移方程？
答：
- 明确状态含义（如
dp[i]表示前i个元素的最优解）。 - 分析最后一步决策（如爬楼梯最后一步是走 1 步还是 2 步）。
- 用状态转移方程关联当前状态与子状态（如
dp[i] = max(dp[i-1], dp[i-2] + val)）。
问题 3：0-1 背包和完全背包的 DP 状态转移有何不同？
答：0-1 背包每个物品只能选一次，内层循环容量 w 需逆序（避免重复选同一物品）；完全背包可无限选，内层循环正序（允许重复选同一物品）。
贪心思想
核心思想
每一步选择当前局部最优解，期望通过局部最优达到全局最优。适用于具有贪心选择性质（局部最优解能构成全局最优解）和最优子结构的问题。
关键要素
- 贪心策略：定义每一步的选择规则（如 “选当前最小”“选性价比最高”）。
- 正确性证明：需证明贪心策略的局部最优可推导全局最优（常用反证法、数学归纳法）。
经典例子
- 活动选择问题：选择不重叠的最多活动，每次选最早结束的活动。
- Dijkstra 算法：求单源最短路径，每次选当前距离最小的节点更新邻居。
- 霍夫曼编码：每次合并频率最小的两个节点，生成最优前缀码。
面试官常见问题
问题 1：贪心算法一定能得到最优解吗？举例说明。
答：不一定。例如 0-1 背包问题，贪心（选性价比最高）可能无法得到最优解（因受容量限制，需组合选择）。但分数背包问题（物品可分割）中贪心有效，因局部最优即全局最优。
问题 2：如何证明贪心策略的正确性？
答：通常用交换论证：假设存在一个最优解与贪心解不同，通过交换步骤证明贪心解至少不比该最优解差，从而说明贪心解是最优的。例如活动选择问题中，最早结束的活动一定在某个最优解中，否则可替换为该活动得到相同或更优解。
问题 3：贪心和 DP 的适用场景对比？
答：
- 贪心：适合问题具有贪心选择性质，每一步局部最优可推导全局最优，时间复杂度低（通常线性）。
- DP：适合子问题重叠且需全局最优，需存储状态，时间复杂度为子问题数量 × 转移时间（如 O (n²)）。
DFS（深度优先搜索）与 BFS（广度优先搜索）思想
核心思想
- DFS：从起点出发，尽可能深地探索分支，直到无法继续后回溯，用栈（递归或显式栈）实现。
- BFS：从起点出发，按层遍历，先访问所有邻居，再逐层深入，用队列实现。
核心区别
| 特性 | DFS | BFS |
|---|---|---|
| 数据结构 | 栈（递归栈或显式栈） | 队列 |
| 遍历顺序 | 深度优先（先访问子节点，再回溯） | 广度优先（按层访问，先访问父节点的所有邻居） |
| 适用场景 | 找所有路径、连通性、回溯问题 | 最短路径（无权图）、层序遍历、找最少步数 |
| 空间复杂度 | O (深度)（可能栈溢出，如树深度大时） | O (宽度)（适合分层处理，内存更可控） |
经典例子
- DFS：
- 迷宫找所有出口路径（回溯法）。
- 图的连通分量检测（标记已访问节点）。
- 生成子集 / 排列（递归枚举选择或不选）。
- BFS：
- 无权图的最短路径（记录每个节点的层数）。
- 二叉树层序遍历（按层输出节点）。
- 社交网络中找 “一度、二度好友”（按距离分层）。
面试官常见问题
问题 1：DFS 和 BFS 的时间复杂度是多少？
答：均为 O(V+E)，其中 V 是节点数，E 是边数。DFS 遍历所有节点和边，BFS 同理（每个节点入队一次，每条边处理一次）。
问题 2：如何用 DFS/BFS 判断图中是否存在环？
答：
- DFS：访问节点时标记为 “正在访问”，若在子树中发现已访问且状态为 “正在访问” 的节点，则存在环（适用于有向图和无向图）。
- BFS：不适用于有向图环检测（需记录前驱），无向图中若邻居已访问且不是前驱，则存在环。
问题 3：在树结构中，DFS 和 BFS 分别对应哪些遍历方式？
答：
- DFS：对应先序（根左右）、中序（左根右）、后序（左右根）遍历。
- BFS：对应层序遍历（按层从上到下、从左到右）。
总结
- DP：解决重叠子问题和最优子结构问题，需定义状态和转移方程。
- 贪心：每一步选局部最优，需证明策略正确性，适合特定结构问题。
- DFS/BFS：图和树的遍历工具，DFS 适合深度探索和回溯，BFS 适合分层和最短路径。