每日算法 — 使用java实现斜率优化DP：凸包技巧与动态规划转移加速
算法概述 斜率优化动态规划（Slope Trick / Convex Hull Trick for DP）是一种用于优化特定形式动态规划转移的高级技巧。当DP转移方程形如： dp[i] = min{dp[j] + cost(j, i)} for j < i...
标签： 斜率优化
每日算法 — 使用java实现斜率优化DP：单调队列维护凸包加速动态规划
引言 动态规划（DP）是算法竞赛和工程实践中最核心的技术之一。当DP转移方程形如 $dp[i] = \min_{j < i}{dp[j] + a[i] \cdot b[j] + c[i] + d[j]}$ 时，朴素的 $O(n^2)$...
每日算法 — 使用java实现李超线段树：动态半平面交与最优线段查询
引言 在计算几何和动态规划中，经常遇到这样的问题：维护一组直线，支持插入一条直线和查询某 x...
每日算法 — 使用java实现斜率优化：动态规划凸包优化与决策单调性
引言 斜率优化（Slope Optimization / Convex Hull Trick）是动态规划的高级优化技巧，适用于状态转移方程形如 dp[i] = min(dp[j] + cost(j, i)) 且 cost...
