区间dp介绍

区间dp

区间dp的数据量一般都是三位数(<=300)，简单的基本都是O(n^3)的作法。~难点~就是三层循环中最里面的那层循环，因题而异。
即在解决1-i内所有子区间的问题后，新增了一个元素，如何更新区间值。新加入i后，循环从i-1到1，逆向更新。(dp里循环的顺序也是很重要啊，其实就是看区间内的解依赖哪部分区间的以求解)

for (int i=1;i<2*n;i++){
        for (int j=i-1;j>=1;j--){
            for (int k=j;k<i;k++){
                dp[j][i] = max(dp[j][i],oper());
            }
        }
    }

当涉及到“环”时，n就要变成2n了。最里面那层循环是合并两个区间时，如何取最优的问题。若要优化成O(n^2)的作法，基本就是只能优化最里面那层循环了，看需要。