所刷的题及素材大部分出自提高课，可能不全面，蒟蒻见解，如有错误，请及时指出

使用

顾名思义，处理对区间做划分的动态规划问题
可以看成合并/拆分一段连续的区间，求出对应的答案。

思路

要求整个区间的答案，可以把他分成求每个子区间的最优解，子区间同理划分。当区间划分到最小时划分结束。然后每个子区间向上合并，算出原区间最优解，最终算出整个区间的答案。
上面是记忆化搜索的过程。不过我们写代码时一般直接从最小划分区间向上合并。
具体细节看下面代码。

具体操作和代码

for(int len = 1; len < n; len ++)   // 首先枚举长度，也就是每个小区间
    for(int l = 1; l + len <= n; l ++) // 枚举区间的左端点
    {
        int r = l + len;            // 区间的右端点
        for(int k = l; k < r; k ++) // 枚举间断点，即区间(l,r) 由子区间(l,k)和(k,j)组成。
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + X) // 转移方程
    }

其中各种边界：按照题意进行分析。

1. 长度len：起点为一次合并的数的个数，终点为答案所在的区间的长度。
   例：1068. 环形石子合并 ，每次只合并两个数，初始为1，答案区间长度n，所以$len<n$。
   320. 能量项链，一次合并3个数，初始为2，答案区间长度为$n+1$，所以$len < n + 1$

2. 间断点k：具体题意具体分析，通常的情况(l,k)和(k,r)，
   (l,k)和(k+1,r)，(l,k)和(k,r)，(l,k-1)和 k 和(k+1,r)。
   第一种：1069. 凸多边形的划分 在$(l,r)$中选一个点连接两个边界点，中间的选的点是共用的。
   第二/三种： 321. 棋盘分割 选择一条线分割，分为上下两个区间，中间不共用。
   第四种：479.加分二叉树 在$[l,r]$中找一个点做根，然后分成左右两个子树。

trick(技巧)

处理环形问题时，可以将整个链状在原来的基础上重复一次。然后在两倍的区间上做区间dp。

通常都可以转化成记忆化搜索来做。

练习

牛客NC13230.合并回文字串

题意

给两个字符串，将他们以不改变在原序列中的顺序合并，所能构成的最长回文串是多少。

思路

双重区间DP。

设两个字符串的区间分别为 [i1,j1],[i2,j2]。
$i$是每个字符串区间的第一个字符（下面代表$i1$或$i2$），$j$则是最后一个字符（下面代表$j1$或$j2$）。

能够转移到这个区间的子区间为 头加一，尾减一，即i+1,j-1，两两组合则有四种情况。
因为需要构成回文串，所以第一个和最后一个字符串相等则表示可以转移。
即任意的$i$和$j$能匹配上就可以构成回文串。

初始化，两个区间总共的字符数小于等于一的时候也是回文串。
并且在这题中，对一个区间来说选一个字符时端点为i == j，而不选时i = j - 1。
即不选的区间是[i,i-1],正常来说$i到i-1$这个区间似乎是不合法的，但是这里表示的是一个字符都不选的状态所以也初始化为$1$。

这题对我来说还是挺难的QWQ

#include<iostream>
#include<cstring>

using namespace std;

const int N = 55;

int n;
char a[N], b[N];
bool f[N][N][N][N]; // 第一个串[i1,j1]和第二个串[i2,j2]可以合并成回文串。

int main()
{
    cin >> n;
    while(n --)
    {
        memset(f, 0, sizeof f);
        scanf("%s%s", a + 1, b + 1);
        int n1 = strlen(a + 1), n2 = strlen(b + 1);

        int ans = 0;
        for(int len1 = 0; len1 <= n1; len1 ++)
            for(int len2 = 0; len2 <= n2; len2 ++)
                for(int i1 = 1; i1 + len1 - 1 <= n1; i1 ++)
                    for(int i2 = 1; i2 + len2 - 1 <= n2; i2 ++)
                    {
                        int j1 = i1 + len1 - 1, j2 = i2 + len2 - 1;
                        bool &v = f[i1][j1][i2][j2];
                        if(len1 + len2 < 2) v = 1;
                        else
                        {
                            if(a[i1] == a[j1]) v |= f[i1 + 1][j1 - 1][i2][j2];
                            if(a[i1] == b[j2]) v |= f[i1 + 1][j1][i2][j2 - 1];
                            if(b[i2] == a[j1]) v |= f[i1][j1 - 1][i2 + 1][j2];
                            if(b[i2] == b[j2]) v |= f[i1][j1][i2 + 1][j2 - 1];
                        }
                        if(v) ans = max(ans, len1 + len2); // 如果区间可构成回文串，判断是否能作为答案
                    }
        cout << ans << endl;
    }

}