算法设计中的经典思想：从分治、贪心到动态规划的思维跃迁

引言：算法不仅是代码，更是思维

很多开发者将"刷题"等同于"学算法"，收获仅仅是几十道题的解法模板。但真正有价值的算法训练，是培养一套面对未知问题时的分析框架——分治、贪心、动态规划这三大思想，构成了算法设计思维的座基。本文不只讲"怎么做"，更讲"怎么想"，通过经典问题的深度拆解，帮助读者建立从问题到算法的直觉映射。

分治法：大问题化小，独立求解合并结果

分治（Divide and Conquer）遵循三步曲：分解原问题为相互独立的子问题，递归求解子问题，合并子问题的解得到原问题的解。其复杂度通常可用主定理T(n)=a·T(n/b)+f(n)分析。

归并排序是分治的经典体现：将数组一分为二，分别排序，再线性合并。每层O(n)共log n层，总时间复杂度O(n log n)，稳定可靠。

func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])
    right := mergeSort(nums[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    l, r := 0, 0
    for l < len(left) && r < len(right) {
        if left[l] <= right[r] {
            result = append(result, left[l])
            l++
        } else {
            result = append(result, right[r])
            r++
        }
    }
    result = append(result, left[l:]...)
    result = append(result, right[r:]...)
    return result
}

分治思想的威力远超排序。快速选择算法（QuickSelect）用于求第k大元素。从中选pivot分区后将递归范围缩小到一半，均摊O(n)，优于堆的O(n log k)。Strassen矩阵乘法也利用分治将朴素O(n^3)降至O(n^2.81)。而最接近点对、大整数乘法（Karatsuba）和FFT更是分治思想在不同领域的绽放。

贪心算法：当下最优的累积就是全局最优

贪心算法每次选择当前状态下的局部最优解，绝不回退，期望累积出全局最优。它的证明通常用到「交换论证」（Exchange Argument）或「拟阵理论」（Matroid Theory）。

活动选择问题是一类经典的贪心场景：给定n个任务的开始和结束时间，选出最多个互不重叠的步骤。虽然按最早开始、最短时长或最少冲突做的贪心策略都可能得到错误结果，按最早结束时间排序后的贪心选择才是正确的——这背后的直觉是结束得越快留给后续任务的空间就越大。

def max_activities(activities):
    # 按结束时间排序
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

# 正确性证明要点（交换论证）：
# 设贪心解为 G = {g1, g2, ...}，最优解为 O = {o1, o2, ...}
# 由于 g1 结束时间最早，必有 end(g1) <= end(o1)
# 将 O 中的 o1 替换为 g1，O 仍然有效（不减少活动数）
# 对子问题递归应用此论证，可得 |G| = |O|

更多成功应用包括霍夫曼编码（最优前缀编码）、Dijkstra最短路径、Kruskal最小生成树、分数背包问题、区间覆盖问题。而硬币找零问题（面额为1、5、10）虽然在特定面额下贪心有效，但面额更泛化后只能使用DP求解——这正是贪心与DP的分野所在。

动态规划：最优子结构下的记忆化递归

动态规划（DP）适用于两种特征同时成立的问题——最优子结构（大问题的最优解包含小问题的最优解）和重叠子问题（不同的求解路径中同一子问题被反复计算）。

四个步骤构成的通用框架：定义dp数组存储状态，提取状态转移方程，确定初始条件和边界，决定遍历顺序以利用已知的子问题结果。

0/1背包问题是DP最经典的入门题——给定n个物品各自的重量和价值，在总重量限制下求最大价值。状态dp[i][w]表示前i个物品在容量w时的最大价值，状态转移即为不放（dp[i‑1][w]）和放（dp[i‑1][w‑weight[i]] + value[i]）的较大者。空间压缩后dp[w]逆序迭代即可。上述框架还可以应用到最长公共子序列、最大子数组和、编辑距离、股票交易系列以及正则表达式匹配等更广泛的问题上。

三种思想的对比与选择

结语：思维跃迁之路

分治训练你"分解问题"的能力，贪心培养你"证明当下选择最优性"的直觉，动态规划教你"记忆化避免重复计算"。它们并非孤立存在——分治可以带记忆化（如矩阵链乘既可用分治也可DP实现），贪心是DP的特例（当DP的转移退化为单一最优分支时）。真正的高手面对新问题时，会下意识地问子问题是否独立？当前选择是否可证明为全局最优？有无重叠子问题可复用？——这三个问题将引领你找到适合的算法设计方向。