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

用最小信息定义有效状态

用最小信息定义有效状态

动态规划建模的关键不是先写转移方程,而是先回答:计算走到当前位置时,哪些信息会真正改变后续选择与答案?本节用“可区分的未来”判断状态是否缺信息、是否冗余,并区分状态语义与存储维度。

学习目标

  • 能从题目约束中提取决定后续结果的最小信息
  • 能用反例判断状态是否少了一维或携带无用维度
  • 能区分“状态需要几维”和“实现需要存几维”

状态只保留会影响未来的信息

一个状态之所以有效,是因为所有被归入这个状态的历史,在后续可执行的选择、约束和收益计算上都等价。换句话说,过去发生了什么并不重要;只要那些差异不会改变未来,就不应继续保留。

例如股票交易中,处理到第 i 天后,仅记录“当前最大利润”是不够的。利润同为 5 时,一种历史可能手里持股,另一种可能空仓;下一天价格上涨时,两者允许的动作不同。因此至少要区分时间位置和持仓状态,可写成 dp[i][0] 与 dp[i][1]。

股票交易状态最小信息示意图

判断某条信息是否应该进入状态,可以做一个简单的反事实测试:固定其他信息,只改变这一项,如果未来允许的转移或最终最优值可能发生变化,这项信息就不能删;如果无论怎么改变都不会影响未来,它就是冗余信息。

用反例检查状态是否缺信息

发现状态过少最可靠的方法,不是继续推公式,而是构造“两段历史被错误合并”的反例。仍以股票交易为例,如果把状态写成 dp[i],就会把持股与空仓合并。此时“今天能否卖出”无法从 dp[i] 判断,说明状态定义已经丢失必要信息。

约束增加时,状态也可能需要增加维度。若题目限制最多完成 k 次交易,那么“已使用多少次交易”会影响未来还能否买卖,因此可进一步写成 dp[i][k][h],其中 h 表示是否持股。反过来,如果交易次数无限制,k 就不再决定未来,把它保留在状态中只会扩大状态空间。

状态维度不等于存储维度

状态语义必须完整,但实现时可以利用依赖关系压缩存储。股票无限次交易的完整语义仍然包含“第几天”和“是否持股”,可是一旦第 i 天只依赖第 i-1 天,就没有必要保存所有天的表格,只需保留上一层的两个值。

下面的程序用 cash 表示当天结束后空仓的最大利润,用 hold 表示当天结束后持股的最大利润。更新时先保存旧值,避免同一天的新状态反过来参与本轮计算。

python
def max_profit(prices):
    cash = 0
    hold = -prices[0]

    for price in prices[1:]:
        old_cash, old_hold = cash, hold
        cash = max(old_cash, old_hold + price)
        hold = max(old_hold, old_cash - price)

    return cash

prices = [7, 1, 5, 3, 6, 4]
print(max_profit(prices))

预期输出:

text
7

这里虽然只存了两个变量,但并不意味着问题只剩“零维状态”。时间维度被计算顺序隐式承载,持仓维度被两个变量显式承载。先证明状态正确,再做空间压缩,比一开始追求最少数组维度更稳妥。

识别冗余信息

状态过多通常表现为:某个维度不同,但它们的后续转移完全一致。例如无限次股票交易中,如果额外记录“此前具体在哪一天买入”,只要当前是否持股和当前最优利润已经确定,买入日期本身并不会改变下一天的合法动作,因此不应成为状态维度。

可以用三步检查状态是否最小:先尝试删掉一个字段,再寻找两个会被合并但未来不同的历史;若找不到,再检查该字段是否只用于解释过去而不影响未来。最终保留下来的状态,应当既足以唯一决定后续转移,又不保存可以由其他状态或计算顺序推导出的信息。

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

目录与阅读设置

阅读设置

17

记录一个想法

用最小信息定义有效状态

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

登录哪都通