1D/1D 动态规划

状态数为 O(n)、每个状态有 O(n) 个决策的 DP 形式;给出无后效条件。

标签 动态规划 / 1D/1D / DP 优化

模型

设 𝑛∈ℕ,𝑉 为全序集,𝐿,𝑅:{1,…,𝑛}→ℤ 满足 1≤𝐿(𝑖)≤𝑅(𝑖)<𝑖(1≤𝑖≤𝑛)。

记 𝐷={(𝑖,𝑗):1≤𝑖≤𝑛,𝐿(𝑖)≤𝑗≤𝑅(𝑖)}。

对每个 (𝑖,𝑗)∈𝐷,给定 𝑄𝑖,𝑗:𝑉→𝑉。

1D/1D 动态规划是求 𝑓:{1,…,𝑛}→𝑉,使得

𝑓(𝑖)=min𝐿(𝑖)≤𝑗≤𝑅(𝑖)𝑄𝑖,𝑗(𝑓(𝑗)).

其中 𝐿(𝑖),𝑅(𝑖) 分别是 𝑓(𝑖) 的决策下标下界与上界;条件 𝑅(𝑖)<𝑖 保证 𝑓(𝑖) 只依赖已经求出的 𝑓(𝑗)。

若固定 𝑖,𝑗 后 𝑄𝑖,𝑗(𝑣) 可在 𝑂(1) 时间求值,则直接计算所有 𝑓(𝑖) 的时间为 𝑂(𝑛2)。

源码位置