区间类动态规划之详解凸多边形的划分

区间动态规划是线性动规的拓展，在划分阶段时，往往是以区间的长度从小到大为阶段，逐步求解到到长度为N的区间的最优值，在枚举每一个区间的最优值时，由于当前区间内又有很多种合并方式并到到当前区间，那么就需要枚举这些合并方式中产生的值维护最优值，合并的不同，可以看作是区间划分的不同，划分时需要枚举划分的位置，即分割点。 　　那么对于区间类动态规划问题，往往可以将问题分解成为两两合并的形式。其解决方法是对整个问题设最优解，枚举分割点，维护最优值。 dp[i][j] = max{dp[i][k] + dp[k+1][j] + 合并时需要计算的值 },其中k为区间[i,j]内一分割点。 回到问题凸多边形的划分这道题。 题目描述 　　给定一个具有N（N n; for(int i=1;i> a[i]; for(int i= 1;i