1D/1D 动态规划
状态数为 O(n)、每个状态有 O(n) 个决策的 DP 形式;给出无后效条件。标签 动态规划 / 1D/1D / DP 优化
模型
设 , 为全序集, 满足 ()。
记 。
对每个 ,给定 。
1D/1D 动态规划是求 ,使得
其中 分别是 的决策下标下界与上界;条件 保证 只依赖已经求出的 。
若固定 后 可在 时间求值,则直接计算所有 的时间为 。
标签 动态规划 / 1D/1D / DP 优化
设 , 为全序集, 满足 ()。
记 。
对每个 ,给定 。
1D/1D 动态规划是求 ,使得
其中 分别是 的决策下标下界与上界;条件 保证 只依赖已经求出的 。
若固定 后 可在 时间求值,则直接计算所有 的时间为 。