【区间dp-回文-5】leet 1745. 分割回文串 IV --是否可以分成3段回文子串
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd" 输出：true 解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy" 输出：false 解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000s 只包含小写英文字母。
本题在用动态规划构建dp[l][r]之后，
需要有2个指针i和j，闭区间[0,i]第一个字符串，闭区间[i+1,j]第二个字符串，闭区间[j+1,n-1]第三个字符串，判断是否满足3个条件都是true；其中 0<=i <n-2, i+1<=j<n-1;
public boolean checkPartitioning(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int r = 0; r < s.length(); r++) {
for (int l = r; l >= 0; l--) {
if (l == r || (s.charAt(l) == s.charAt(r) && (l + 1 == r ||
dp[l + 1][r - 1] == true))) {
dp[l][r] = true;
}
}
}
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1]) return true;
}
}
return false;
}
类似题目：
同系列题目：
算法笔试-动态规划系列 文章被收录于专栏
动态规划相关算法笔试题
