【算法学习】动态规划的斜率优化

本文主要是介绍【算法学习】动态规划的斜率优化，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

动态规划的状态转移方程为\(dp[i] = min(dp[j] + f(i,j)) , L(i)<=j<=R(i)\)
若\(f(i,j)\)仅与i，j中的一个有关，则可以采用单调队列优化，若\(f(i,j)\)与\(i,j\)均有关，则可以采用斜率优化
例题：
HDU3507
容易写出状态转移方程：
\(dp[i] = min(dp[j] + (s[i] - s[j])^2) + m , 0=<j<i\)
枚举一遍i，枚举一遍j的话时间复杂度是 \(n^2\)
使用斜率优化可以做到\(On\)
上面方程变换后，可看成一元线性方程y=kx+b：
\(dp[j]+s[j]^2=2s[i]*s[j]+dp[i]-s[i]^2-m\)
\(y = dp[j]+s[j]^2 , k =2s[i],x = s[j],b=dp[i]-s[i]^2-m\)

在二维坐标系考虑决策：
我们要求dp[i]最小，即b最小。 每一个决策j对应坐标系中的一个点\((s[j],dp[j]+s[j]^2)\)
将直线y=kx+b自下向上平移，第一次接触到的决策点b最小，就是最小的dp[i]

采用单调队列时需要注意两个问题：
1.处理过时决策点
枚举i ，斜率k是递增的，当前最优决策左侧的点已经过时，所以每次都将相邻两点线段斜率小于等于k的过时决策出队。这样队头就是最优决策

2.维护下凸壳
横坐标s[j]随着j的递增而递增，因此新的决策必然出现在下凸壳最右端。所以检查队列尾部两个点和第i个点是否下凸，若不满足，则队尾出队，直到满足，将i加入队列尾部。

这篇关于【算法学习】动态规划的斜率优化的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！