1、破环成链。没有太多的技巧性,具体而言就是把数据存储两遍,使得环形的数据可以链式展开,便于我们去DP。
但最后一定要记得扫一遍答案,取F[i][i+N-1],i:1->N中的最大/小值。
2、前缀和。这个东西并不是在所有情况下都适用,但使用起来真的很方便,可以把O(n)的复杂度优化为O(1)。不过只适用于需要把数据直接相加的地方,比如说这道题。
3、初始化。这里实际上包括两点,一方面是在某些特殊情况下需要初始化,初始化为某特定值(比如本题只分成1段的时候)。另一方面也就是数组初始化,求最大值的时候根本不用管(因为初始默认为0),在求最小值的时候把数组全部赋初值为极大值就好啦。
4、状态表达。一般来说可以用F[i][j]表示在区间[i,j]中怎么怎么样,但由于本题还加了一个分为几段的状态,就把数组直接加一维就好了。