算法竞赛专题解析│四边形不等式优化( 五 ) ：算法竞赛专题解析│四边形

dp[i][j]=min{dp[i][k?1]+dp[k+1][j]+w(i,j)?e[k]}
w(i,j)是区间和， w(i,j)=fi+fi+1+...+fj 。当把两棵左右子树连在根结点上时，本身的深度增加1 ，所以每个元素都多计算一次，这样就解决了cost(ei)的计算。最后，因为根节点k的层数是0 ，所以减去根节点的值e[k] 。
w(i,j)符合四边形不等式优化的条件，所以dp[i][j]可以用四边形不等式优化。
09
参考书籍
《算法竞赛入门到进阶》
ISBN：978-7-302-52915-6
罗勇军郭卫斌编著
定价：59.8元
10
精彩文章回顾
算法竞赛专题解析│A*搜索
算法竞赛专题解析│广搜进阶
算法竞赛专题解析│剪枝
算法竞赛专题解析│搜索基础
算法竞赛专题解析│简单数据机构
算法竞赛专题解析│并查集
算法竞赛专题解析│尺取法
算法竞赛专题解析│二分法、三分法
Spark算法实例：词频统计大数据集群的部署实例｜附视频
用Excel制作工资条实例｜附素材+视频
真题解析│2017年蓝桥杯软件类省赛传统“送分题”
Java15新增类Record的工作实例｜附代码
Dart应用Bloc设计模式实例｜附代码
从火种到能源，华为做AI的逻辑链
华为AI ，建造中的全景图
逻辑回归的MATLAB实践｜附代码
Python爬虫实例：采集微博博文｜附视频
MySQL利用E-R模型的数据库概念设计｜附视频
HTML5实现黑白棋游戏附代码