从局部最优到分而治之再到全局最优递推一篇吃透三大算法思想前言在算法设计与面试中有三种策略是绝对绕不开的核心贪心算法、分治算法、动态规划。它们各自代表了不同的思维方式贪心走一步看一步选当前最好的分治大问题拆小逐个击破再合并动态规划记住过去用子问题的解推导当前本文将系统讲解这三种策略的原理、适用条件、经典问题实战以及它们之间的对比与联系。目录贪心算法分治算法动态规划三大策略对比总结如何选择一张决策图一、贪心算法 (Greedy)1.1 核心思想每一步都选当前看起来最优的选择期望通过局部最优的累积达到全局最优。一句话只顾眼前不管将来。1.2 两个关键性质性质含义贪心选择性质全局最优解可以通过一系列局部最优选择得到最优子结构问题的最优解包含子问题的最优解只有同时满足这两个性质的问题贪心才能保证最优解。1.3 经典问题一活动选择问题描述有 n 个活动每个活动有开始时间 s[i] 和结束时间 f[i]。一个人同一时间只能参加一个活动求最多能参加多少个活动。贪心策略每次选结束时间最早且不冲突的活动。pythondef activity_selection(activities): activities: list of (start, end) 返回最多能参加的活动数量 # 按结束时间排序 activities.sort(keylambda x: x[1]) count 1 last_end activities[0][1] for i in range(1, len(activities)): if activities[i][0] last_end: count 1 last_end activities[i][1] return count # 测试 acts [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)] print(activity_selection(acts)) # 输出: 3为什么正确结束越早留给后面的时间越多可以用交换法证明。1.4 经典问题二分数背包问题描述有 n 个物品每个物品有重量 w[i] 和价值 v[i]背包容量为 C。物品可以拆分拿一部分求最大价值。贪心策略按单位重量价值v[i]/w[i]从高到低拿。pythondef fractional_knapsack(items, capacity): items: list of (value, weight) capacity: 背包容量 # 按单位价值降序排序 items.sort(keylambda x: x[0]/x[1], reverseTrue) total_value 0 remaining capacity for value, weight in items: if remaining weight: # 整个拿走 total_value value remaining - weight else: # 拿走剩余容量的一部分 total_value value * (remaining / weight) break return total_value # 测试 items [(60, 10), (100, 20), (120, 30)] # (价值, 重量) print(fractional_knapsack(items, 50)) # 输出: 2401.5 经典问题三霍夫曼编码问题描述给定字符及其出现频率构造前缀码使总编码长度最短。贪心策略每次合并频率最小的两个节点。pythonimport heapq class Node: def __init__(self, freq, chNone, leftNone, rightNone): self.freq freq self.ch ch self.left left self.right right def __lt__(self, other): return self.freq other.freq def huffman_coding(freq_dict): freq_dict: {a: 45, b: 13, ...} 返回编码字典 heap [Node(freq, ch) for ch, freq in freq_dict.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) parent Node(left.freq right.freq, leftleft, rightright) heapq.heappush(heap, parent) # 生成编码 codes {} def dfs(node, code): if node.ch is not None: codes[node.ch] code return dfs(node.left, code 0) dfs(node.right, code 1) dfs(heap[0], ) return codes # 测试 freq {A: 45, B: 13, C: 12, D: 16, E: 9, F: 5} codes huffman_coding(freq) print(codes)1.6 贪心的局限性重要0-1背包问题物品不能拆分时贪心失效。python# 物品(价值, 重量) items [(60, 10), (100, 20), (120, 30)] capacity 50 # 贪心按单位价值先拿60(10) 100(20) 160剩余20不够拿120 → 总价值160 # 最优解不拿60拿100(20) 120(30) 220 print(fractional_knapsack(items, 50)) # 分数背包240 # 0-1背包最优是220贪心只得到160失败二、分治算法 (Divide and Conquer)2.1 核心思想分而治之将原问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题递归求解子问题然后将子问题的解合并成原问题的解。一句话大事化小小事化了最后再合并。2.2 三个步骤步骤说明分解 (Divide)将原问题分解成若干个规模较小的子问题解决 (Conquer)递归地求解子问题。子问题足够小时直接求解合并 (Combine)将子问题的解合并成原问题的解2.3 经典问题一归并排序pythondef merge_sort(arr): if len(arr) 1: return arr # 1. 分解 mid len(arr) // 2 left merge_sort(arr[:mid]) right merge_sort(arr[mid:]) # 2. 合并 return merge(left, right) def merge(left, right): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result # 测试 arr [38, 27, 43, 3, 9, 82, 10] print(merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]复杂度时间 O(n log n)空间 O(n)2.4 经典问题二快速排序pythondef quick_sort(arr, left0, rightNone): if right is None: right len(arr) - 1 if left right: pivot_index partition(arr, left, right) quick_sort(arr, left, pivot_index - 1) quick_sort(arr, pivot_index 1, right) return arr def partition(arr, left, right): pivot arr[right] # 选最后一个为基准 i left - 1 for j in range(left, right): if arr[j] pivot: i 1 arr[i], arr[j] arr[j], arr[i] arr[i 1], arr[right] arr[right], arr[i 1] return i 1 # 测试 arr [38, 27, 43, 3, 9, 82, 10] print(quick_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]2.5 经典问题三最大子数组和分治版问题找出数组中连续子数组的最大和。分治策略最大子数组要么在左半边要么在右半边要么跨越中点。pythondef max_subarray(nums, left, right): if left right: return nums[left] mid (left right) // 2 # 左半边最大 left_max max_subarray(nums, left, mid) # 右半边最大 right_max max_subarray(nums, mid 1, right) # 跨越中点的最大 cross_max cross_subarray(nums, left, mid, right) return max(left_max, right_max, cross_max) def cross_subarray(nums, left, mid, right): # 从中点向左扩展 left_sum float(-inf) curr 0 for i in range(mid, left - 1, -1): curr nums[i] left_sum max(left_sum, curr) # 从中点向右扩展 right_sum float(-inf) curr 0 for i in range(mid 1, right 1): curr nums[i] right_sum max(right_sum, curr) return left_sum right_sum # 测试 nums [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(max_subarray(nums, 0, len(nums) - 1)) # 输出: 6子数组[4,-1,2,1]注这个问题有更高效的 Kadane 算法动态规划 O(n)这里仅展示分治思想。2.6 经典问题四二分查找最简单的分治应用每次将搜索范围减半。pythondef binary_search(arr, target): left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1 # 测试 arr [1, 3, 5, 7, 9, 11] print(binary_search(arr, 7)) # 输出: 3三、动态规划 (Dynamic Programming)3.1 核心思想记住过去避免重复计算将原问题分解成若干个子问题先求解子问题然后从子问题的解逐步推导出原问题的解。与分治的区别是子问题之间不是独立的会有重叠。一句话用空间换时间把重复计算的结果存起来。3.2 两个关键性质性质含义最优子结构问题的最优解包含子问题的最优解重叠子问题子问题会被反复计算多次3.3 解题模板五步法text步骤1确定dp数组的含义dp[i]表示什么 步骤2确定状态转移方程如何从子问题推导 步骤3初始化边界条件最小的子问题 步骤4确定遍历顺序从小到大或从上到下 步骤5手动演算验证3.4 经典问题一斐波那契数列最简单的 DP 入门问题。pythondef fib(n): if n 1: return n # 1. dp数组含义dp[i] 第i个斐波那契数 dp [0] * (n 1) # 3. 初始化 dp[0], dp[1] 0, 1 # 4. 遍历顺序从小到大 for i in range(2, n 1): # 2. 状态转移方程 dp[i] dp[i - 1] dp[i - 2] return dp[n] # 空间优化版只用两个变量 def fib_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b return b print(fib(10)) # 输出: 553.5 经典问题二爬楼梯问题每次可以爬 1 或 2 个台阶爬到 n 阶有多少种不同方法pythondef climb_stairs(n): if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n] print(climb_stairs(5)) # 输出: 83.6 经典问题三0-1背包最经典的DP问题n 个物品每个有重量 w[i] 和价值 v[i]背包容量 C每种物品只能选一次求最大价值。pythondef knapsack_01(weights, values, capacity): n len(weights) # dp[i][c] 表示前i个物品容量c时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): w weights[i - 1] v values[i - 1] for c in range(1, capacity 1): if c w: # 装不下当前物品 dp[i][c] dp[i - 1][c] else: # 装或不装取最大值 dp[i][c] max(dp[i - 1][c], dp[i - 1][c - w] v) return dp[n][capacity] # 空间优化版一维数组 def knapsack_01_optimized(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 必须倒序遍历防止重复使用 for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], dp[c - weights[i]] values[i]) return dp[capacity] # 测试 weights [2, 3, 4, 5] values [3, 4, 5, 6] capacity 8 print(knapsack_01(weights, values, capacity)) # 输出: 10选234? 实际358? 验证345? 容量不对3.7 经典问题四最长递增子序列 (LIS)问题找出数组中最长的严格递增子序列的长度。pythondef length_of_lis(nums): if not nums: return 0 n len(nums) # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度 dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp) # 更优解法贪心二分 O(n log n) def length_of_lis_optimized(nums): import bisect tails [] for num in nums: pos bisect.bisect_left(tails, num) if pos len(tails): tails.append(num) else: tails[pos] num return len(tails) nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis(nums)) # 输出: 4[2,3,7,101]或[2,5,7,101]四、三大策略对比总结维度贪心算法分治算法动态规划核心思想每步选局部最优大拆小合小成大记录子问题递推求解子问题关系独立一次决策相互独立重叠依赖是否需要记录子问题解❌ 不需要❌ 不需要递归✅ 需要DP表能否保证全局最优❌ 不一定✅ 保证✅ 保证时间复杂度O(n log n) 常见O(n log n) 常见O(n²) 或 O(n³) 常见空间复杂度O(1) 或 O(n)O(log n) 或 O(n)O(n) 或 O(n²)典型应用活动选择、霍夫曼码、最小生成树归并排序、快排、二分查找背包、LCS、最短路径五、如何选择一张决策图快速判断表问题特征推荐算法子问题相互独立 可以合并分治子问题重叠 有最优子结构动态规划每一步选最优 不影响后续贪心子问题独立 规模递减明显分治如二分查找需要所有解回溯/DFS求最优解 可分解DP 或 贪心六、实战练习题推荐贪心算法LeetCode 55. 跳跃游戏LeetCode 45. 跳跃游戏 IILeetCode 435. 无重叠区间分治算法LeetCode 53. 最大子数组和LeetCode 169. 多数元素LeetCode 241. 为运算表达式设计优先级动态规划LeetCode 70. 爬楼梯LeetCode 300. 最长递增子序列LeetCode 1143. 最长公共子序列LeetCode 322. 零钱兑换七、总结算法一句话总结适用场景贪心走一步看一步选当前最好的有贪心选择性质的问题分治大问题拆小逐个击破再合并子问题相互独立动态规划记住过去用子问题推导当前子问题重叠 最优子结构学习建议先从分治入手理解递归和问题分解再学动态规划掌握状态转移和递推思想最后学贪心理解其适用条件和局限性记住贪心是最快的但不是总对的分治是最自然的但不一定最有效DP是最通用的但成本也最高。