数据结构与算法 / 系统课时
在压缩空间后恢复最优方案
在压缩空间后恢复最优方案
滚动数组可以把动态规划的状态值压缩到常数空间,但被覆盖的状态往往正是恢复最优路径需要的信息。本篇分析这一冲突,并用决策记录与局部重算在较小内存下同时保留最优值和一条完整方案。
学习目标
- 区分计算最优值所需状态与恢复最优方案所需信息
- 根据决策数量选择前驱、决策位或局部重算策略
- 在滚动状态已经压缩后恢复一条一致的最优路径
状态值能压缩不代表路径也能压缩
许多一维动态规划在计算 dp[i] 时只依赖前一两个状态,因此可以用几个变量替代完整 dp 数组。例如 dp[i] = max(dp[i-1], dp[i-2] + value[i]) 只需要保留最近两个最优值。
但最终的一个最优值并没有说明它是从哪条转移得到的。若所有历史状态和选择都被覆盖,程序通常只能回答“最优值是多少”,无法倒推“具体选择了哪些位置”。
因此要分别考虑两类信息:前向计算需要保存多少数值状态,以及反向恢复需要留下多少决策证据。空间优化时真正应该压缩的是前者,而不是无条件删除后者。
三种恢复策略的取舍
最直接的方法是为每个状态记录完整前驱下标。恢复时从终点沿前驱链回溯即可,实现简单且适用于复杂转移,但需要 O(n) 级额外空间,有时会抵消滚动数组的收益。
如果每个状态只有少量选择,例如“取或不取”“来自左侧或上方”,则只记录决策编号即可。二选一甚至只需要一个比特;计算最优值仍可使用滚动变量,而恢复信息远小于保存完整数值状态。
当状态数极大、连决策记录也希望减少时,可以保留稀疏检查点,再在恢复阶段重新计算某个局部区间。它用额外计算时间换内存,但要求转移可以根据检查点可靠重放,因此并非所有动态规划都适用。

用决策位保留一条最优路径
下面以“不选择相邻位置并使总价值最大”为例。最优值只需要两个滚动变量,同时用 bytearray 为每个位置保存一次“取或不取”的决策。示例在价值相同时固定选择“不取当前项”,从而保证恢复过程具有确定性。
def select_non_adjacent(values):
n = len(values)
if n == 0:
return 0, []
# take[i] 为 1 表示 dp[i] 的最优解选择了位置 i。
take = bytearray(n)
dp_minus2 = 0
dp_minus1 = 0
for i, value in enumerate(values):
choose_current = dp_minus2 + value
skip_current = dp_minus1
if choose_current > skip_current:
current = choose_current
take[i] = 1
else:
current = skip_current
# 数值状态只保留最近两个前缀结果。
dp_minus2, dp_minus1 = dp_minus1, current
selected = []
i = n - 1
while i >= 0:
if take[i]:
selected.append(i)
i -= 2
else:
i -= 1
selected.reverse()
return dp_minus1, selected
best, positions = select_non_adjacent([2, 7, 9, 3, 1])
print('best =', best)
print('positions =', positions)预期输出
best = 12
positions = [0, 2, 4]前向计算的最优值状态仍是 O(1),而恢复信息为每个位置一个决策字节;若使用真正的位集合,还可以继续压缩常数因子。反向过程每次根据决策移动一格或两格,因此恢复时间为 O(n)。
什么时候必须保存更多信息
决策位成立的前提是,一个很小的选择编号足以确定回溯方向。如果一个状态可能从大量不同前驱转移而来,只记录“选择了某类操作”仍无法定位具体前驱,此时应记录前驱下标或其他足以唯一重建路径的信息。
还要注意,压缩后的滚动状态不能在回溯阶段直接访问。若选择局部重算,就必须明确保存哪些边界状态能够重新生成目标区间,并保证重算使用与首次计算完全相同的转移和并列决策规则,否则可能得到最优值相同但路径不一致的结果。
空间压缩与方案恢复并不矛盾:数值状态可以根据依赖范围滚动覆盖,而恢复证据应按实际选择数量单独设计。先确定回溯需要回答什么,再决定记录前驱、记录紧凑决策,还是接受额外计算进行局部重放。