1745. 分割回文串 IV
链接: 1745. 分割回文串 IV
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = “abcbdd”
输出：true
解释：“abcbdd” = “a” + “bcb” + “dd”，三个子字符串都是回文的。
示例 2：
输入：s = “bcbddxy”
输出：false
解释：s 没办法被分割成 3 个回文子字符串。
解法：
算法思路：
题⽬要求⼀个字符串被分成「三个⾮空回⽂⼦串」，乍⼀看，要表⽰的状态很多，有些⽆从下⼿。
其实，我们可以把它拆成「两个⼩问题」：
i. 动态规划求解字符串中的⼀段⾮空⼦串是否是回⽂串；
ii. 枚举三个⼦串除字符串端点外的起⽌点，查询这三段⾮空⼦串是否是回⽂串。
那么这道困难题就免秒变为简单题啦，变成了⼀道枚举题
代码：
bool checkPartitioning(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
dp[0][0]=1;
for(int j=1;j<n;j++)
{
dp[j][j]=1;
for(int i=0;i<=j;i++)
{
if(s[i]==s[j])
{
if(j==i+1) dp[i][j]=1;
if(j>i+1) dp[i][j]=dp[i+1][j-1];
}
}
}
for(int i=1;i<n-1;i++)
{
for(int j=0;j<i;j++)
{
if(dp[0][j]&&dp[j+1][i]&&dp[i+1][n-1])
return true;
}
}
return false;
}
132. 分割回文串 II
链接: 132. 分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2：
输入：s = “a”
输出：0
示例 3：
输入：s = “ab”
输出：1
算法思路：
- 状态表⽰：
根据「经验」，继续尝试⽤ i 位置为结尾，定义状态表⽰，看看能否解决问题：
dp[i] 表⽰： s 中 [0, i] 区间上的字符串，最少分割的次数
1.状态表示*
根据「经验」，继续尝试⽤ i 位置为结尾，定义状态表⽰，看看能否解决问题：
dp[i] 表⽰： s 中 [0, i] 区间上的字符串，最少分割的次数⽂串。
2.状态转移方程
状态转移⽅程⼀般都是根据「最后⼀个位置」的信息来分析：设 0 <= j <= i ，那么我们可以根据 j ~ i 位置上的⼦串是否是回⽂串分成下⾯两类：
- i. 当 [j ,i] 位置上的⼦串能够构成⼀个回⽂串，那么 dp[i] 就等于 [0, j - 1] 区 间上最少回⽂串的个数+1，即
dp[i] = dp[j - 1] + 1 ； - ii. 当 [j ,i] 位置上的⼦串不能构成⼀个回⽂串，此时 j 位置就不⽤考虑。
3. 初始化
观察「状态转移⽅程」，我们会⽤到 j - 1 位置的值。我们可以思考⼀下当 j == 0 的时候，表⽰的区间就是 [0, i] 。如果 [0, i] 区间上的字符串已经是回⽂串了，最⼩的回⽂串就是 了， j 往后的值就不⽤遍历了。
因此，我们可以在循环遍历 j 的值之前处理 j == 0 的情况，然后 j 从 1 开始循环。
但是，为了防⽌求 min 操作时， 0 ⼲扰结果。我们先把表⾥⾯的值初始化为「⽆穷⼤」
4. 填表顺序
从左往右
5. 返回值
根据「状态表⽰」，应该返回 dp[n - 1]
代码：
int minCut(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
dp[0][0]=1;
for(int j=1;j<n;j++)
{
dp[j][j]=1;
for(int i=0;i<=j;i++)
{
if(s[i]==s[j])
{
if(j==i+1) dp[i][j]=1;
if(j>i+1) dp[i][j]=dp[i+1][j-1];
}
}
}
vector<int> dp1(n,INT_MAX-500);
dp1[0]=0;
for(int i=1;i<n;i++)
{
if(dp[0][i]) dp1[i]=0;
else
{
for(int j=1;j<=i;j++)
{
if(dp[j][i])
dp1[i]=min(dp1[i],dp1[j-1]+1);
}
}
}
return dp1[n-1];
}