区间DP

分为$区间分割$、$区间合并$

区间分割:$$n长度的序列，分割为k部分，每部分有权值，求如何分割才能使得总权值最优$$

区间DP三步骤

一、读题

二、定义

f[n][k]=s;

f[i][j] 表示长度为i的序列分成j部分的最大值

三、状态转移方程

f[i][j]=f[i][k]+f[k+1][j]+s[i~j]

四、初始化，边界值

表初始化为一个极大值memset(f,0x3f,sizeof(f)); f[i][i]=0

五、答案 f[1][n]

以下为写法

写法1:

for(int j=1;j<=n;j++){
    for(int i=j;i<=n;i++>){
        for(int k=j;k<=i-1;k++>){
               ……
        }
    }
}

写法2:

for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++>){
        for(int k=j;k<=i-1;k++>){
               ……
        }
    }
}