【动态规划刷题 18】（hard）回文子串&& （hard）最长回文子串

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;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

132. 分割回文串 II

链接: 132. 分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2：

输入：s = “a”
输出：0
示例 3：

输入：s = “ab”
输出：1

算法思路：

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];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36