本文主要是介绍斜率优化dp结论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
斜率优化dp
一切的前提为:k<j<i,假设从j转移到i比从k转移到i更优(即靠后的j优),去按照题目推导不等式,如果得到g(k,j)<f(i),因为想在决策i的时候f(i)其实为常量,我们设为C=f(i),则将前述不等式表述一般化:
定理:对于下标k<j,如果g(k,j)<C,则靠后的j更优;否则,g(k,j)>C,靠前的k更优。
结论:如果g(i,j)<C,最后求最优解时维护下凸包。
证明:设由k<j<i向后面的x点转移,如果维护下凸包的话,且k,j,i都保留在凸包上的话,
就应该有g(k,j)<g(j,i). 利用反证法,先假设g(k,j)>g(j,i),只需证明在这个情况下,j肯定不会在下凸包上(即j肯定不会成为最优集中的点)即可。
1) 如果g(j,i)<C ==> i比j优,故j没用(由红色定理部分推得)
2) 如果g(j,i)>C,因我们已经假设g(k,j)>g(j,i),而g(j,i)>C,故g(k,j)>C,k更优,既然k更优,则j又没用。
综上能说明,在g(k,j)>g(j,i)时,j不在凸包上(即不在最优集上),故矛盾,因此有g(k,j)<g(j,i),
所以要维护下凸包.
这篇关于斜率优化dp结论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!