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

处理相邻元素不能同时选择

处理相邻元素不能同时选择

当相邻位置不能同时选时,难点不是“选哪些元素”,而是让每个位置只依赖已经求出的更小问题。本篇把“选择当前位置”和“跳过当前位置”拆成两条来源,建立线性动态规划,并处理首尾相连时的额外冲突。

学习目标

  • 能写出相邻元素互斥问题的状态定义与转移式
  • 能用两个滚动变量把空间从 O(n) 压缩到 O(1)
  • 能把线性模型扩展到首尾相连的环形序列

把冲突写成状态转移

设 dp[i] 表示只考虑下标 0...i 时能取得的最大总和。走到位置 i 时只有两种合法决策:跳过它,答案仍是 dp[i-1];选择它,则位置 i-1 必须跳过,因此来源是 dp[i-2] + nums[i]。

因此核心转移只有一句:dp[i] = max(dp[i-1], dp[i-2] + nums[i])。这一步把“不能选相邻元素”的约束直接编码进了状态来源,而不需要事后检查冲突。

相邻元素互斥的两种状态来源

边界可以从空前缀开始理解:尚未处理任何元素时最优值为 0。若允许一个元素,则最大值是 max(0, nums[0])。当题目明确保证元素非负时,这与常见的 dp[0] = nums[0] 等价。

用滚动变量实现线性版本

转移只依赖前两个状态,所以没有必要保存整张 dp 数组。下面的实现同时保留线性版本和首尾相连版本,便于直接验证两种边界。

python
def max_non_adjacent_sum(nums):
    prev2 = 0  # 相当于 dp[i-2]
    prev1 = 0  # 相当于 dp[i-1]

    for value in nums:
        current = max(prev1, prev2 + value)
        prev2, prev1 = prev1, current

    return prev1

def max_circular_non_adjacent_sum(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return max(0, nums[0])

    # 首尾不能同时选择,因此只需比较两个互不包含首尾冲突的线性区间。
    return max(
        max_non_adjacent_sum(nums[:-1]),
        max_non_adjacent_sum(nums[1:]),
    )

if __name__ == "__main__":
    values = [2, 7, 9, 3, 1]
    print("linear:", max_non_adjacent_sum(values))
    print("circular:", max_circular_non_adjacent_sum(values))

预期输出:

text
linear: 12
circular: 11

prev2 和 prev1 在每轮更新前分别代表前两个阶段的最优值。更新顺序必须同时完成;若先覆盖 prev1 再计算 prev2,就会丢失旧状态。

首尾相连为什么要拆成两次线性问题

环形序列多出一个约束:下标 0 与下标 n-1 也相邻。任何合法解都不可能同时包含这两个位置,因此完整解一定落在两类情况之一:不选最后一个,只看 0...n-2;或不选第一个,只看 1...n-1。

分别对这两个线性区间执行同一个转移,再取较大值即可。这里不需要为“环”重新设计复杂状态,因为首尾冲突可以通过互斥分支被完整覆盖。

识别状态设计是否正确

一个可靠的检查方法是问:当决定选择当前位置时,转移来源是否已经保证所有冲突都被排除。如果仍需回头检查相邻位置,说明状态定义还没有把约束吃进去。

对于线性序列,这个模型的时间复杂度是 O(n),滚动变量版本的额外空间是 O(1)。若题目改成“相邻距离小于 k 的位置都不能同时选”,思路仍然相同,只是“选择当前位置”时需要跳回更早的合法阶段。

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

目录与阅读设置

阅读设置

17

记录一个想法

处理相邻元素不能同时选择

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

登录哪都通