数据结构与算法 / 系统课时

从题意到代码完成综合建模

从题意到代码完成综合建模

综合动态规划题真正困难的地方,通常不是写出循环,而是把题目的选择限制、最优目标和方案计数同时压进可转移的状态。本节用一个完整问题走完从暴力枚举、状态设计到复杂度优化的全过程。

学习目标

  • 从暴力选择过程识别重复子问题,并据此定义状态
  • 在同一套转移中同时维护最优值与最优方案数量
  • 用边界、样例和复杂度反查模型,再完成空间优化

从暴力选择开始拆问题

考虑这样一个问题:给定整数数组,每个位置可以选或不选,但不能同时选择相邻位置。要求返回所选数字的最大总和,以及达到最大总和的不同下标选择方案数量。

如果直接枚举,每个位置都有“选”和“不选”两种决定。遇到选择某个位置后,下一个位置必须跳过,因此最自然的暴力搜索状态是“处理到哪里、上一个位置是否被选择”。最坏情况下仍会产生指数级分支。

真正值得观察的是:无论前面通过哪条选择路径到达位置 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}。

python
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}")

预期输出

text
best=2, ways=3

这里最容易漏掉的不是状态数量,而是“并列最优时方案数相加”。如果只用 max() 选一条来源,就会正确得到最大值,却丢失另一条同样最优的路径。

用边界和复杂度反查模型

写完转移后不要立刻结束,可以用三个问题反查模型。首先,空数组应该返回 (0, 1),因为空选择本身是一种方案;其次,单元素数组必须能在“选”和“不选”之间正确比较;最后,如果题目允许负数,还要确认是否允许一个元素都不选,因为这会改变答案定义。

原始暴力枚举需要探索指数级选择组合。动态规划只对每个元素更新两个状态,因此时间复杂度降为 O(n)O(n)。如果把每个位置的两个状态都存进数组,空间复杂度是 O(n)O(n);由于第 i 步只依赖第 i-1 步,本例进一步压缩成了 O(1)O(1) 空间。

这种优化必须放在模型正确之后完成。先写清状态含义和来源,再观察依赖范围决定是否滚动数组,比一开始直接追求一维变量更不容易把旧状态覆盖错。

把综合题稳定地落到代码

面对新的综合题,可以沿同样的链路推进:先写出最直接的选择或搜索过程,确认每一步有哪些决定;再问后续究竟需要记住哪些历史信息,把这些信息定义成状态;接着为每个状态枚举合法来源,并明确多目标或计数在并列时如何合并。

最后再检查初始状态是否代表真实业务含义、答案落在哪个状态、时间和空间复杂度能否通过数据规模。只有这些问题都能回答,空间压缩、状态合并或其他优化才有可靠依据。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

从题意到代码完成综合建模

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通