算法设计三大经典策略：贪心 / 分治 / 动态规划 详解与实战

从局部最优到分而治之，再到全局最优递推，一篇吃透三大算法思想

前言

在算法设计与面试中，有三种策略是绝对绕不开的核心：贪心算法、分治算法、动态规划。

它们各自代表了不同的思维方式：

• 贪心：走一步看一步，选当前最好的

• 分治：大问题拆小，逐个击破再合并

• 动态规划：记住过去，用子问题的解推导当前

本文将系统讲解这三种策略的原理、适用条件、经典问题实战，以及它们之间的对比与联系。

目录

1. 贪心算法

2. 分治算法

3. 动态规划

4. 三大策略对比总结

5. 如何选择：一张决策图

一、贪心算法 (Greedy)

1.1 核心思想

每一步都选当前看起来最优的选择，期望通过局部最优的累积达到全局最优。

一句话：只顾眼前，不管将来。

1.2 两个关键性质

只有同时满足这两个性质的问题，贪心才能保证最优解。

1.3 经典问题一：活动选择

问题描述：有 n 个活动，每个活动有开始时间 s[i] 和结束时间 f[i]。一个人同一时间只能参加一个活动，求最多能参加多少个活动。

贪心策略：每次选结束时间最早且不冲突的活动。

python

def activity_selection(activities): """ activities: list of (start, end) 返回：最多能参加的活动数量 """ # 按结束时间排序 activities.sort(key=lambda 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]）从高到低拿。

python

def fractional_knapsack(items, capacity): """ items: list of (value, weight) capacity: 背包容量 """ # 按单位价值降序排序 items.sort(key=lambda x: x[0]/x[1], reverse=True) 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)) # 输出: 240

1.5 经典问题三：霍夫曼编码

问题描述：给定字符及其出现频率，构造前缀码，使总编码长度最短。

贪心策略：每次合并频率最小的两个节点。

python

import heapq class Node: def __init__(self, freq, ch=None, left=None, right=None): 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, left=left, right=right) 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 三个步骤

2.3 经典问题一：归并排序

python

def 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 经典问题二：快速排序

python

def quick_sort(arr, left=0, right=None): 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 经典问题三：最大子数组和（分治版）

问题：找出数组中连续子数组的最大和。

分治策略：最大子数组要么在左半边，要么在右半边，要么跨越中点。

python

def 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 经典问题四：二分查找

最简单的分治应用：每次将搜索范围减半。

python

def 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 入门问题。

python

def 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)) # 输出: 55

3.5 经典问题二：爬楼梯

问题：每次可以爬 1 或 2 个台阶，爬到 n 阶有多少种不同方法？

python

def 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)) # 输出: 8

3.6 经典问题三：0-1背包（最经典的DP）

问题：n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量 C，每种物品只能选一次，求最大价值。

python

def 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（选2+3+4? 实际3+5=8? 验证：3+4+5? 容量不对）

3.7 经典问题四：最长递增子序列 (LIS)

问题：找出数组中最长的严格递增子序列的长度。

python

def 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]）

四、三大策略对比总结

五、如何选择？一张决策图

快速判断表

六、实战练习题推荐

贪心算法

• LeetCode 55. 跳跃游戏

• LeetCode 45. 跳跃游戏 II

• LeetCode 435. 无重叠区间

分治算法

• LeetCode 53. 最大子数组和

• LeetCode 169. 多数元素

• LeetCode 241. 为运算表达式设计优先级

动态规划

• LeetCode 70. 爬楼梯

• LeetCode 300. 最长递增子序列

• LeetCode 1143. 最长公共子序列

• LeetCode 322. 零钱兑换

七、总结

学习建议：

1. 先从分治入手，理解递归和问题分解

2. 再学动态规划，掌握状态转移和递推思想

3. 最后学贪心，理解其适用条件和局限性

记住：贪心是最快的，但不是总对的；分治是最自然的，但不一定最有效；DP是最通用的，但成本也最高。