算法策略

五大算法策略：核心思想、经典问题与适用场景

算法策略是解决问题的方法论，不同策略适用于不同类型的问题。掌握分治、贪心、动态规划、回溯、分支界限五大策略的核心特征，能帮助我们快速选择合适的算法思路，高效解决复杂问题。

分治法（Divide and Conquer）：分而治之

核心特征

• 问题拆分：将原问题拆分为规模更小、结构相同的子问题（子问题相互独立，无重叠）。
• 递归求解：递归解决每个子问题，再将子问题的解合并为原问题的解。
• 无重复计算：子问题独立，无需存储中间结果（与动态规划的核心区别）。

经典问题

• 归并排序：将数组拆分为两个子数组，排序后合并（合并过程是关键）。
• 快速排序：选基准元素拆分数组为左右两部分，递归排序后直接拼接（无需显式合并）。
• 二分搜索：将有序数组拆分为左右两部分，通过比较目标值与中间值缩小范围。
• 汉诺塔：将 n 个盘子的问题拆分为 n-1 个盘子的子问题，递归移动盘子。

适用场景

• 问题可拆分为独立子问题，且子问题解法与原问题一致（递归结构清晰）。
• 合并子问题的成本低于直接求解原问题（如归并排序的合并步骤复杂度为 O (n)，整体效率优于 O (n²)）。

贪心法（Greedy Algorithm）：局部最优的累积

核心特征

• 局部最优选择：每一步都选择当前状态下的最优解（如价值最高、成本最低），不回溯。
• 全局近似解：通过累积局部最优解得到全局解，但未必是真正最优解（除非问题满足 “贪心选择性质”）。

经典问题

• 找零钱问题：在面额为 {1,5,10,20} 的货币体系中，优先选最大面额，可得到最少硬币数（满足贪心选择性质）。
• 部分背包问题：物品可分割，优先选单位重量价值最高的物品，可得到最优解。
• 最小生成树（Kruskal/Prim 算法）：Kruskal 按边权重从小到大选边（避圈），Prim 从顶点出发选最短邻边，均通过贪心得到最优树。
• 迪杰斯特拉算法：求解单源最短路径，每次选当前距离起点最近的顶点，更新邻边距离。

局限性

• 仅在问题满足 “贪心选择性质”（局部最优必然导致全局最优）时有效。
• 0-1 背包问题中贪心失效：选价值最高的物品可能导致剩余容量浪费，不如组合低价值物品总价值高。

动态规划法（Dynamic Programming, DP）：存储子问题的最优解

核心特征

• 最优子结构：原问题的最优解包含子问题的最优解。
• 重叠子问题：子问题不独立，多个大问题共享相同子问题（与分治法的核心区别）。
• 自底向上求解：用数组 / 表格存储子问题的最优解，避免重复计算，逐步构建原问题的解。

经典问题

• 斐波那契数列：f(n) = f(n-1) + f(n-2)，用数组存储f(0)到f(n-1)，避免递归的重复计算（时间复杂度从 O (2ⁿ) 降至 O (n)）。
• 0-1 背包问题：用二维数组dp[i][j]存储 “前 i 件物品在容量 j 下的最大价值”，通过子问题结果推导当前状态。
• 最长公共子序列（LCS）：dp[i][j]表示 “字符串 A 前 i 个字符与字符串 B 前 j 个字符的 LCS 长度”，通过子问题组合求解。
• 矩阵链乘法：通过拆分矩阵链为子链，存储最优拆分方案的最小计算量。

与分治法的区别

维度	分治法	动态规划
子问题关系	独立（无重叠）	重叠（共享子问题）
计算方式	递归求解，不存储子问题结果	存储子问题结果，自底向上计算
典型应用	归并排序、二分搜索	背包问题、LCS

回溯法（Backtracking）：深度优先的试错搜索

核心特征

• 系统搜索：按深度优先策略遍历问题的解空间树（每个节点代表一种选择）。
• 剪枝回溯：当某条路径无法到达目标（或非最优）时，退回上一步（撤销选择），尝试其他路径。
• 穷举 + 剪枝：本质是带剪枝的穷举，确保不遗漏可能的解。

经典问题

• N 皇后问题：在 N×N 棋盘上放置 N 个皇后，确保互不攻击。通过回溯撤销无效位置的皇后，尝试下一列放置。
• 迷宫求解：从起点出发，沿一个方向探索，走不通则退回上一岔路口，尝试其他方向。
• 子集和问题：从数组中选子集，使其和等于目标值。通过回溯添加 / 移除元素，剪枝超过目标和的路径。

适用场景

• 解空间有限且需找到所有解或任一解（如排列组合、约束满足问题）。
• 问题存在明确的约束条件（便于剪枝，减少无效搜索）。

分支界限法（Branch and Bound）：广度优先的最优搜索

核心特征

• 解空间树遍历：与回溯法类似，但按广度优先或最小耗费优先策略遍历（而非深度优先）。
• 界限剪枝：为每个节点计算 “下界”（最小值问题）或 “上界”（最大值问题），剪去不可能包含最优解的分支。
• 优先队列：常用优先队列（如最小堆）存储待扩展节点，优先处理更可能接近最优解的节点。

经典问题

• 旅行商问题（TSP）：寻找访问所有城市的最短回路。通过计算部分路径的下界，剪去长于当前最优解的路径。
• 0-1 背包问题（优化版）：用分支界限法可在找到一个可行解后，通过上界剪去不可能更优的分支，效率高于动态规划（尤其大规模数据）。
• 任务分配问题：将 n 项任务分配给 n 个人，使总耗时最小。通过计算部分分配的下界，剪去无效分支。

与回溯法的区别

维度	回溯法	分支界限法
搜索策略	深度优先	广度优先 / 最小耗费优先
目标	找到所有解或任一解	找到最优解（通常唯一）
剪枝依据	约束条件（是否可行）	界限（是否可能最优）

总结：如何选择算法策略

策略	核心思想	适用场景	典型问题
分治法	拆分独立子问题，递归合并	问题可拆分且子问题独立	归并排序、二分搜索
贪心法	局部最优累积，不回溯	满足贪心选择性质的优化问题	找零钱、最小生成树
动态规划	存储重叠子问题的最优解	有最优子结构和重叠子问题的最优解问题	0-1 背包、LCS
回溯法	深度优先试错，回溯剪枝	需所有解或任一解，解空间有限	N 皇后、子集和
分支界限法	广度 / 耗费优先，界限剪枝	需最优解，解空间大但可通过界限剪枝	TSP、大规模背包问题