LC5666. 回文串分割 IV(区间dp)

题意

判断字符串能否分解为三段回文子串。

---

思路

因为 n ≤ 2000 n\le 2000 n≤2000，所以可以 n 2 n^2 n2预处理判断任意区间 [ l , r ] [l,r] [l,r]是否回文串。
然后暴力枚举两个割点即可。

因为回文串是往外扩展的，所以区间 d p dp dp是可行的。

---

const int N=2e3+5;
bool dp[N][N];
class Solution {
public:
    bool checkPartitioning(string s) {
        memset(dp,false,sizeof dp);
        int n=s.size();
        for(int l=1;l<=n;l++)
            for(int i=0;i+l-1<n;i++){
                int j=i+l-1;
                if(l==1) dp[i][j]=1;
                else if(l==2) dp[i][j]=(s[i]==s[j]);
                else dp[i][j]=(s[i]==s[j]&&dp[i+1][j-1]);
            }
        for(int i=1;i<n;i++)
            for(int j=i;j+1<n;j++)
                if(dp[i][j]&&dp[0][i-1]&&dp[j+1][n-1]) return true;
                return false;
    }
};