对于区间DP这类问题，关键还是在于思考，将问题看出用区间DP的思路解决后再一步步将大区间化小，变成一个个小区间后进行实现。

上次提到的区间DP模板，是三重循环，现在我们进行优化（在寻找区间最佳位置时耗费了大量时间）（我们可以在枚举分割点的时候将这个点保存下来）
用s[i][j]表示区间[i,j]中的最优分割点，那么第三重循环可以从[i,j-1)优化到【s[i][j-1],s[i+1][j]】。(这个时候小区间s[i][j-1]和s[i+1][j]的值已经求出来了，然后通过这个循环又可以得到s[i][j]的值)。

另外对于区间DP问题，可能对于一题有多种变形（正逆两种情形）
例：
括号匹配问题（可以问括号的配对情况，也可以问增添多少次括号达到配对）（增删括号与字符串增删构成回文串类似）
n堆石子合并求代价最小问题（可以延伸为n堆石子在圆周上求代价最小问题）等
所以做完一道题目的时候可以再去看它的变形题，类似题。

对于区间DP，很多时候都没有思路，即使讲过的题目也只是当时有了大体思路，下课后再去想，会了讲过的，还是对其他题目难有思路，对于区间DP的模板的原理清楚了，却套不到问题中去。 。 。

对常数进行赋值：
const ll mod = 1e9+7; //mod=1000000007
const ll INF = 1e18; //INF=1000000000000000000(18位）
const double eps = 1e-9; //eps=0.000000001