每日一题 3.26 合并回文子串

这是一道区间dp的题
我们设置这样一个数组 dp[l1][r1][l2][r2] 来代表字符串 s1 s2 选择的范围
那么递推方程怎么来 对于这样一个方程 它只能由这四种情况得来
dp[l1+1][r1][l2][r2-1] dp[l1+1][r1-1][l2][r2]
dp[l1][r1][l2+1][r2-1] dp[l1][r1-1][l2+1][r2]
如果相对应的字符相等而且它的子情况有一种是真的 dp[l1][r1][l2][r2] 为真
所以递推方程就得到了
PS：注意区间dp的枚举是区间长度

#include <bits/stdc++.h>
using namespace std;
#define  ll long long 
int dp[55][55][55][55];
char s1[55], s2[55];
int main(){
    int t; scanf("%d", &t);
    while(t--){
        memset(dp, 0, sizeof(dp));
        scanf("%s%s", s1+1, s2+1);
        int len1=strlen(s1+1), len2=strlen(s2+1), ans=0;
        for(int i=0; i<=len1; i++){///s1长度
            for(int j=0; j<=len2; j++){///s2长度
                for(int l1=1, r1=l1+i-1; r1<=len1; l1++, r1++){///s1起点终点
                    for(int l2=1, r2=l2+j-1; r2<=len2; l2++, r2++){///s2起点终点
                        if(i+j<=1) dp[l1][r1][l2][r2]=1;///总长度只有一
                        else{
                            if(s1[l1]==s1[r1]&&r1>0) dp[l1][r1][l2][r2]|=dp[l1+1][r1-1][l2][r2];///以s1的左右字符结尾
                            if(s1[l1]==s2[r2]&&r2>0) dp[l1][r1][l2][r2]|=dp[l1+1][r1][l2][r2-1];///以s1的左 s2的右字符结尾
                            if(s2[l2]==s2[r2]&&r2>0) dp[l1][r1][l2][r2]|=dp[l1][r1][l2+1][r2-1];///以s2的左 s2的右字符结尾
                            if(s2[l2]==s1[r1]&&r1>0) dp[l1][r1][l2][r2]|=dp[l1][r1-1][l2+1][r2];///以s2的左 s1的右字符结尾
                        }
                        if(dp[l1][r1][l2][r2]) ans=max(ans, r1-l1+r2-l2+2);///寻找最大的字符串组合
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}