标签:动态规划
16 个条目
-
概念 最大子段和
求数组中和最大的连续非空子段;前缀和最小值与 Kadane 扫描给出两种等价视角。
2026-11-17 -
在加减表达式中任意加括号使结果最大;只需要考虑减号后的括号,括号层数不超过两层,三状态 DP。
2026-11-17 -
题目 加权单机区间调度
单机选择不重叠区间,使总权值最大;按右端点排序,用 DP 加二分前驱求解。
2026-11-17 -
概念 1D/1D 动态规划
状态数为 O(n)、每个状态有 O(n) 个决策的 DP 形式;给出无后效条件。
2026-11-15 -
概念 动态规划
动态规划的一般模型:状态集合、有限转移集合、子问题集合、状态充分性与值代数;循环引用时转为 Bellman 方程。
2026-11-15 -
概念 半环
带合并运算 ⊕ 与组合运算 ⊗ 的代数结构;定义分配律、吸收律与单位元。
2026-11-14 -
概念 二分栈优化 DP
当 Q_(i,j) 可依赖 f(j)、最优决策满足决策单调性中的单交叉条件时,用二分栈在线维护决策区间,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
概念 多重背包
每种物品有数量上限;在容量约束下选择件数,最小化总费用;给出 f(i,j) 转移、边界与变式。
2026-11-13 -
概念 决策单调性
最优决策点 J(i) 随 i 单调;每个决策的最优位置连续。单交叉是更强的两两比较条件。
2026-11-13 -
概念 分治优化决策单调DP
当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
概念 单调队列优化 DP
当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。
2026-11-13 -
概念 单调队列优化多重背包
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。
2026-11-13 -
概念 前缀信息优化 DP
当转移只依赖前缀且 i、j 的贡献可分离时,维护 y(j,f(j)) 的前缀聚合,把 O(n^2) 的转移降为 O(n)。
2026-11-13 -
概念 线段树优化 DP
可分离转移的决策窗口任意时,用线段树维护 y(j,f(j)) 的区间最小值;若候选值随 i 区间加,则配合懒标记维护区间最值。
2026-11-13 -
概念 斜率优化 DP
当 Q_(i,j) 含 A(i)B(j) 时,把转移化为点与直线的截距,用下凸壳查询切线;按 X、K、窗口的单调性选择凸壳维护方式。
2026-11-13 -
概念 Bellman 方程
把值函数写成一步转移后的自身:V=T(V);讨论 Bellman 算子、折扣压缩、单调性与不动点,以及值迭代。
2026-11-13