分治、贪心、回溯和动态规划：识别四种求解思路

问题与目标

复杂问题常由子问题、选择和状态构成。分治、贪心、回溯和动态规划提供四种组织求解过程的视角，但它们不是可以按题目关键词机械套用的模板。

完成标准：能判断四种思想的关键条件，并用动态规划解决一个有约束的小问题。

分治关注拆分与合并，贪心依赖局部选择可以导向整体结果，回溯系统探索选择空间，动态规划则复用重叠子问题。它们对应不同的问题条件，不能只凭题面关键词套用。

核心概念

• 分治：拆成相互独立或相似的子问题，分别求解后合并，如归并排序。
• 贪心：每一步选择当前最优，并且需要证明局部选择能导向全局最优。
• 回溯：枚举选择，发现不可能时撤销，适合排列、组合和约束满足。
• 动态规划：重叠子问题加最优子结构；定义状态、转移、初值和计算顺序。

回溯可能是指数级，剪枝只减少实际搜索量，不改变最坏情况本质。动态规划通常用空间换时间，但状态定义错误会得到稳定而错误的答案。

四种思路的最小例子

分治先拆再合：归并排序把左右两半分别排序。贪心只保留当前最好选择，例如在结束时间最早的任务中选择最多不重叠区间，但这一策略需要证明，不能迁移到所有“最大收益”问题。

回溯的代码骨架包含选择、递归和撤销：

def combinations(values: list[int], size: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def search(start: int) -> None:
        if len(path) == size:
            result.append(path.copy())
            return
        for index in range(start, len(values)):
            path.append(values[index])
            search(index + 1)
            path.pop()

    search(0)
    return result


print(combinations([1, 2, 3, 4], 2))

输入四个值和组合长度 2，输出六个不重复组合。start 避免重新选择前面的元素，剩余元素不足时还可以提前剪枝。

动态规划的设计顺序

1. 状态：dp[i] 到底表示什么。
2. 选择：当前有哪些合法动作。
3. 转移：当前状态怎样由更小状态得到。
4. 初值：最小问题答案是什么。
5. 顺序：转移依赖的状态必须已经计算。
6. 输出：最终答案位于哪个状态。

可运行实现

问题：每天最多处理一个任务，不能连续两天处理高负载任务，求最大收益。输入是每天高负载任务的收益，跳过一天收益为 0。

def max_non_adjacent_score(scores: list[int]) -> int:
    previous_two = 0
    previous_one = 0

    for score in scores:
        take_today = previous_two + score
        skip_today = previous_one
        current = max(take_today, skip_today)
        previous_two, previous_one = previous_one, current

    return previous_one


cases = [
    ([5, 1, 2, 10, 6, 2], 17),
    ([], 0),
    ([8], 8),
]

for scores, expected in cases:
    result = max_non_adjacent_score(scores)
    print(scores, result)
    assert result == expected

状态 dp[i] 表示考虑到第 i 天时的最大收益。当天要么选择，收益来自前两天状态加当天分数；要么跳过，继承前一天状态。这里只依赖前两个状态，因此把 O(n) 状态表压缩为 O(1) 额外空间。

输入是每天的任务收益列表，输出是不能连续选择时的最大总收益。示例覆盖普通、空输入和单元素，并通过断言验证结果。若收益允许负数，当前实现自然选择全部跳过；业务若要求至少选一个，状态初值必须调整。

四种思想可以用同一问题检查：

进一步验证

1. 让收益列表包含负数，分别讨论“可以不选”和“至少选一个”的初始状态。
2. 先写二维或一维状态表，打印每一步的状态，验证后再压缩成两个变量。
3. 构造一个“当前收益最大就选”失败的反例，说明为什么不能直接用贪心。

检查结果应包含状态定义、转移来源、初值、边界样例和一个与穷举小数据的对照测试。

常见问题与排查

• 贪心只因样例通过就认为正确：寻找反例或给出交换论证。
• 回溯忘记恢复现场：选择、递归、撤销三步必须对称。
• 动态规划只有转移式：还必须说明状态含义、初值和遍历方向。
• 记忆化递归无限增长：检查状态是否真正缩小，以及缓存键是否完整。
• 过早压缩空间：先写清状态表并验证，再做滚动变量优化。
• 看到“最大”就使用动态规划：先检查是否存在重叠子问题；没有重复计算时，分治或直接遍历更合适。

小结

四种思想回答不同问题：怎样拆分、怎样选择、怎样枚举、怎样复用。能够写出状态含义或选择理由，比记住某道题的代码更重要。