动态规划-分割回文串ⅡⅣ
在本篇博客中将介绍分割回文串Ⅱ以及分割回文串Ⅳ这两个题目。
分割回文串Ⅱ
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。 返回符合要求的 最少分割次数 。
示例：
输入：s = "aabac"
输出：2
解释：只需2次分割就可将 s 分割成 ["a","aba","c"] 这样3个回文子串。
解题思路
为了解决这个问题，我们可以使用动态规划（Dynamic Programming, DP）的方法。具体来说，我们可以先计算出字符串 s 中所有子串是否是回文串，并存储这个结果，以便后续使用。然后，我们再次使用动态规划来找出将字符串 s 分割成回文子串所需的最少分割次数。
第一步：判断子串是否为回文
我们定义一个二维数组 dp1[i][j]，其中 dp1[i][j] 表示从索引 i 到索引 j 的子串 s[i...j] 是否是回文串。我们可以从字符串的两端向中间遍历，并更新这个数组(这部分与此前回文子串一题中相同 动态规划-回文子串-CSDN博客)。
第二步：动态规划求解最少分割次数
这一步的动态规划思路主要是基于已经判断好的回文子串信息，来求解将整个字符串 s 分割成多个回文子串所需的最少分割次数。这里的关键在于利用动态规划来避免重复计算，并逐步构建出整个问题的解。
- 定义状态：
- 定义
dp2[i]表示将字符串s的前i+1个字符（即s[0...i]）分割成多个回文子串所需的最少分割次数。
- 定义
- 初始化：
dp2[0]初始化为 0，因为空字符串不需要分割。
- 状态转移：
- 对于每个位置
i（从 1 到n-1，其中n是字符串s的长度），我们需要找到所有可能的分割点j（从 0 到i-1），使得s[j+1...i]是一个回文串。这可以通过查询之前计算好的dp1数组来实现，其中dp1[j+1][i]表示s[j+1...i]是否为回文串。 - 如果找到了这样的
j，那么我们可以将s[0...i]分割为s[0...j]和s[j+1...i]两部分，其中s[j+1...i]已经是一个回文串，不需要进一步分割。因此，s[0...i]的最少分割次数就是s[0...j]的最少分割次数（即dp2[j]）加上 1（因为我们在j和i之间进行了一次分割）。 - 我们需要遍历所有可能的
j，并更新dp2[i]为这些分割方案中的最小值。
- 对于每个位置
- 结果：
- 最终，
dp2[n-1]就是整个字符串s的最少分割次数。
- 最终，
代码示例
class Solution {
public:int minCut(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));for (int i = 0; i < n; i++) {dp[i][i] = true; // 单个都是回文子串if (i + 1 < n && s[i] == s[i + 1]) { // 两个相同的字符构成回文子串dp[i][i + 1] = true;}}for (int len = 3; len <= n; len++) { // 从字串长度为3开始遍历for (int i = 0; i < 1 + n - len; i++) { // i+len-1<nint j = i + len - 1;if (s[i] == s[j] && dp[i + 1][j - 1] == true) {dp[i][j] = true;}}}vector<int> f(n,INT_MAX); // f[i]: 从0到i 的子串 所符合要求的 最少分割次数f[0] = 0;for (int i = 1; i < n; i++) {if (dp[0][i] == true) { // 从0到i 的子串是回文串f[i] = 0;} else {for (int j = 0; j <= i; j++) {if (dp[j][i]) {f[i] = min(f[j - 1] + 1, f[i]);}}}}return f[n - 1];}
};分割回文串Ⅳ
题目描述
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdad"
输出：true
解释："abcbdd" = "a" + "bcb" + "dad"，三个子字符串都是回文的。
示例 2：
输入：s = "abaccdef"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
解题思路
这一题与上题相似，要解决这个问题，我们可以采用一种比较直观的方法，即遍历所有可能的分割点，然后检查每个分割点形成的三个子字符串是否都是回文串。为了高效地检查一个子字符串是否是回文串，我们可以先预处理一个二维数组（或者使用一个函数），用于快速判断任意子字符串是否为回文。
第一步：初始化动态规划数组
- 定义一个二维布尔数组
dp，其中dp[i][j]表示字符串s从索引i到索引j（包含两端）的子串是否是回文子串。 - 初始化对角线元素
dp[i][i]为true，因为单个字符自然是回文子串。 - 初始化相邻元素
dp[i][i+1]为true，如果s[i]和s[i+1]相等，因为两个相同的字符也构成回文子串。
第二步：填充动态规划数组
- 使用两层循环遍历所有可能的子串长度（从3开始，因为长度为1和2的情况已经在第一步中处理过了）和起始位置。
- 对于每个子串，检查其首尾字符是否相等，并且去掉首尾字符后的子串（即
dp[i+1][j-1]）是否是回文子串。如果这两个条件都满足，则当前子串是回文子串，将dp[i][j]设置为true。
第三步：检查是否存在有效的分割
- 使用两层循环遍历所有可能的分割点（第一个和第二个分割点），以检查是否存在一种分割方式，使得字符串
s被分为三个非空回文子串。 - 对于每个分割点组合
(i, j)，其中i是第一个分割点的位置（不包括），j是第二个分割点的位置（不包括），检查dp[0][i-1]、dp[i][j-1]和dp[j][n-1]是否都为true。如果是，则表示找到了一个有效的分割方式，返回true。 - 如果遍历完所有可能的分割点组合后都没有找到有效的分割方式，则返回
false。
代码示例
class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));for (int i = 0; i < n; i++) {dp[i][i] = true; // 单个都是回文子串if (i + 1 < n && s[i] == s[i + 1]) { // 两个相同的字符构成回文子串dp[i][i + 1] = true;}}for (int len = 3; len <= n; len++) { // 从字串长度为3开始遍历for (int i = 0; i < 1 + n - len; i++) { // i+len-1<nint j = i + len - 1;if (s[i] == s[j] && dp[i + 1][j - 1] == true) {dp[i][j] = true;}}}for (int i = 0; i < n - 1; 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;}
};