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

前言

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

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

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

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

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

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

---

目录

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 三个步骤

步骤	说明
分解 (Divide)	将原问题分解成若干个规模较小的子问题
解决 (Conquer)	递归地求解子问题。子问题足够小时直接求解
合并 (Combine)	将子问题的解合并成原问题的解

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

---

四、三大策略对比总结

维度	贪心算法	分治算法	动态规划
核心思想	每步选局部最优	大拆小，合小成大	记录子问题，递推求解
子问题关系	独立（一次决策）	相互独立	重叠依赖
是否需要记录子问题解	❌ 不需要	❌ 不需要（递归）	✅ 需要（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. 跳跃游戏 II

• LeetCode 435. 无重叠区间

分治算法

• LeetCode 53. 最大子数组和

• LeetCode 169. 多数元素

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

动态规划

• LeetCode 70. 爬楼梯

• LeetCode 300. 最长递增子序列

• LeetCode 1143. 最长公共子序列

• LeetCode 322. 零钱兑换

---

七、总结

算法	一句话总结	适用场景
贪心	走一步看一步，选当前最好的	有贪心选择性质的问题
分治	大问题拆小，逐个击破再合并	子问题相互独立
动态规划	记住过去，用子问题推导当前	子问题重叠 + 最优子结构

学习建议：

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

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

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

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