数据结构与算法 / 系统课时
处理相邻元素不能同时选择
处理相邻元素不能同时选择
当相邻位置不能同时选时,难点不是“选哪些元素”,而是让每个位置只依赖已经求出的更小问题。本篇把“选择当前位置”和“跳过当前位置”拆成两条来源,建立线性动态规划,并处理首尾相连时的额外冲突。
学习目标
- 能写出相邻元素互斥问题的状态定义与转移式
- 能用两个滚动变量把空间从 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 数组。下面的实现同时保留线性版本和首尾相连版本,便于直接验证两种边界。
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))预期输出:
linear: 12
circular: 11prev2 和 prev1 在每轮更新前分别代表前两个阶段的最优值。更新顺序必须同时完成;若先覆盖 prev1 再计算 prev2,就会丢失旧状态。
首尾相连为什么要拆成两次线性问题
环形序列多出一个约束:下标 0 与下标 n-1 也相邻。任何合法解都不可能同时包含这两个位置,因此完整解一定落在两类情况之一:不选最后一个,只看 0...n-2;或不选第一个,只看 1...n-1。
分别对这两个线性区间执行同一个转移,再取较大值即可。这里不需要为“环”重新设计复杂状态,因为首尾冲突可以通过互斥分支被完整覆盖。
识别状态设计是否正确
一个可靠的检查方法是问:当决定选择当前位置时,转移来源是否已经保证所有冲突都被排除。如果仍需回头检查相邻位置,说明状态定义还没有把约束吃进去。
对于线性序列,这个模型的时间复杂度是 O(n),滚动变量版本的额外空间是 O(1)。若题目改成“相邻距离小于 k 的位置都不能同时选”,思路仍然相同,只是“选择当前位置”时需要跳回更早的合法阶段。