Main
区间动态规划是一种特殊的动态规划方法，它主要用于解决线性结构上的问题，如字符串、数组等。在区间DP中，状态通常由一段区间定义，例如 dp[l][r] 表示从索引 l 到 r 的子区间的某种性质，如最大值、最小值或可能的方案数。
区间DP分为两种，分别为区间分割类DP和区间合并类DP。
区间DP的基本思想
区间DP的核心在于将一个大区间分解成小区间，并通过处理小区间来求解大区间的问题。这种方法通常涉及两个步骤：记忆化搜索和递推。在递推过程中，关键是确定循环的顺序和状态转移方程。大多数区间DP问题都可以通过确定大区间如何转化为小区间，找出边界条件，然后进行动态规划求解。
一、区间分割类型DP
所谓区间分割问题，是指在⻓度为n的线性序列上，分割为k部分，每个部分对应的权值不同，问如何分割才能使总权值最⼤。
我们定义f[i][j] 表示⻓度为 i 的序列，分割为j 部分所能获得的最⼤权值，这是个前i前j问题，那么，我们先考虑最后⼀个分割（即第j个分割）肯定存在⼀个分割点k，使得 k+1 到 i 构成第 j 部分，获得权值和为 w[k+1][i]，那么问题转化为前⾯⻓度为k的序列分割成j-1个部分获得的最⼤权值。
状态转移⽅程：f[i][j] = max(f[k][j-1] + w[k+1][i]) (j-1 ≦ k ≦ i)
有了⼤致的⽅程，针对每道题⽬可能会有⼩调整，随机应变即可。
二、区间合并类型DP
区间合并型DP，我们往往⽤表示区间 i 和 j 的最优值，⽽为了获得这个最优值，往往需要把两个⼦区间进⾏合并得来。为了划分这两个更⼩的区间，我们则需⽤⼀个循环变量 k 来枚举，即将 i 和 j 的区间划分为 i 到 k 的区间和 k+1 到 j 的区间。
状态转移⽅程： f[i][j] = max / min(f[i][j],f[i][k] + f[k+1][j]+(区间合并代价))
代码模板：
int dfs(int l,int r) {
if (r==l)return a[r];
if (f[l][r]!=f[0][0])return f[l][r];
for(int k=l; k<r; k++)f[l][r]=min(f[l][r],dfs(l,k)+dfs(k+1,r)+合并代价);
return f[l][r];
}