1. 斜率优化入门:从暴力DP到高效决策
第一次听说"斜率优化"这个词时,我正被一道动态规划题卡住——明明状态转移方程写对了,提交却总是超时。直到看到前辈的题解里那个神秘的凸包维护过程,才意识到原来DP还能这样玩。斜率优化本质上是用几何思维优化决策过程的高级技巧,特别适合处理具有特定形式的递推关系。
在常规动态规划中,我们经常遇到形如dp[i] = min(dp[j] + cost(j,i))的状态转移方程。当cost函数可以拆分成与i、j相关的独立项时,通过数学变形就能将其转化为直线方程y=kx+b的形式。这时寻找最优决策点j的过程,就变成了在坐标系中寻找使截距b最小的直线,而维护候选决策点的过程则相当于维护一个凸包边界。
关键认知:斜率优化不是某种特定算法,而是一种将代数问题转化为几何问题的通用思想。掌握它需要同时具备动态规划基础和初等几何直觉。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 问题建模与斜率优化原理
2.1 适用场景识别
最经典的斜率优化问题通常具有以下特征:
- 状态转移可表示为dp[i] = min(dp[j] + f(i)*g(j) + h(i) + k(j))
- 存在单调性:决策点j的取值范围随着i增加而单调右移
- 函数f(i)和g(j)至少有一个是单调的(通常题目保证f(i)递增)
以任务调度问题为例:有n个任务,每个任务有执行时间t和代价c,将任务分批处理时每批的代价是该批总t乘以总c,求最小总代价。其状态转移方程为:
dp[i] = min(dp[j] + (sumT[i]-sumT[j]) * sumC[j+1..i])
2.2 代数变形技巧
将上述方程变形为:
dp[i] = min(dp[j] - sumT[i]*sumC[j] + sumT[j]*sumC[j]) + sumT[i]*sumC[i]
令:
- y = dp[j] + sumT[j]*sumC[j]
- x = sumC[j]
- k = sumT[i]
- b = dp[i] - sumT[i]*sumC[i]
方程转化为求使b最小的直线y=kx+b。这意味着我们需要维护一系列(x,y)点,并找到使截距最小的那个点。
3. 凸包维护的三种实现方式
3.1 单调队列解法
当新决策点的x坐标单调递增,且查询斜率k也单调
