数据结构与算法 / 系统课时
从题意到代码完成综合建模
从题意到代码完成综合建模
综合动态规划题真正困难的地方,通常不是写出循环,而是把题目的选择限制、最优目标和方案计数同时压进可转移的状态。本节用一个完整问题走完从暴力枚举、状态设计到复杂度优化的全过程。
学习目标
- 从暴力选择过程识别重复子问题,并据此定义状态
- 在同一套转移中同时维护最优值与最优方案数量
- 用边界、样例和复杂度反查模型,再完成空间优化
从暴力选择开始拆问题
考虑这样一个问题:给定整数数组,每个位置可以选或不选,但不能同时选择相邻位置。要求返回所选数字的最大总和,以及达到最大总和的不同下标选择方案数量。
如果直接枚举,每个位置都有“选”和“不选”两种决定。遇到选择某个位置后,下一个位置必须跳过,因此最自然的暴力搜索状态是“处理到哪里、上一个位置是否被选择”。最坏情况下仍会产生指数级分支。
真正值得观察的是:无论前面通过哪条选择路径到达位置 i,后续决策只关心前一个位置是否被选,以及到达当前状态时已经取得的最好结果。更早的具体选择过程已经没有继续保留的必要。

把目标值和方案数一起放进状态
只记录最大和还不够,因为题目还要求统计有多少种方案达到这个最大和。可以让每个状态保存一对数据:(best, count),分别表示当前状态下的最优值与达到该最优值的方案数量。
处理完当前位置后维护两个状态:
skip:当前位置不选时的(best, count)。take:当前位置被选时的(best, count)。
如果当前位置取值为 x,新的 take 只能来自旧的 skip,因为相邻位置不能同时被选择;新的 skip 则可以来自旧的 skip 或 take。比较两条来源时,如果一方的最优值更大,就保留那一方;如果最优值相同,就把方案数量相加。
初始时还没有处理任何元素,“什么都不选”是一种合法方案,因此 skip=(0, 1)。take 尚不可达,可以把它表示成负无穷和零种方案。
写出可验证的完整转移
下面的程序对数组 [1, 1, 1, 1] 求最大总和与最优方案数。最大和为 2,对应三种下标集合:{0,2}、{0,3} 和 {1,3}。
from math import inf
def better(a: tuple[int, int], b: tuple[int, int]) -> tuple[int, int]:
"""选择最优值更大的状态;若并列则合并方案数量。"""
if a[0] > b[0]:
return a
if b[0] > a[0]:
return b
return a[0], a[1] + b[1]
def max_non_adjacent_with_count(nums: list[int]) -> tuple[int, int]:
# 空前缀只有一种合法选择:什么都不选。
skip = (0, 1)
take = (-inf, 0)
for x in nums:
new_skip = better(skip, take)
# 选择当前位置时,上一位置必须处于 skip 状态。
new_take = (skip[0] + x, skip[1])
skip, take = new_skip, new_take
return better(skip, take)
nums = [1, 1, 1, 1]
best, ways = max_non_adjacent_with_count(nums)
print(f"best={best}, ways={ways}")预期输出
best=2, ways=3这里最容易漏掉的不是状态数量,而是“并列最优时方案数相加”。如果只用 max() 选一条来源,就会正确得到最大值,却丢失另一条同样最优的路径。
用边界和复杂度反查模型
写完转移后不要立刻结束,可以用三个问题反查模型。首先,空数组应该返回 (0, 1),因为空选择本身是一种方案;其次,单元素数组必须能在“选”和“不选”之间正确比较;最后,如果题目允许负数,还要确认是否允许一个元素都不选,因为这会改变答案定义。
原始暴力枚举需要探索指数级选择组合。动态规划只对每个元素更新两个状态,因此时间复杂度降为 。如果把每个位置的两个状态都存进数组,空间复杂度是 ;由于第 i 步只依赖第 i-1 步,本例进一步压缩成了 空间。
这种优化必须放在模型正确之后完成。先写清状态含义和来源,再观察依赖范围决定是否滚动数组,比一开始直接追求一维变量更不容易把旧状态覆盖错。
把综合题稳定地落到代码
面对新的综合题,可以沿同样的链路推进:先写出最直接的选择或搜索过程,确认每一步有哪些决定;再问后续究竟需要记住哪些历史信息,把这些信息定义成状态;接着为每个状态枚举合法来源,并明确多目标或计数在并列时如何合并。
最后再检查初始状态是否代表真实业务含义、答案落在哪个状态、时间和空间复杂度能否通过数据规模。只有这些问题都能回答,空间压缩、状态合并或其他优化才有可靠依据。