算法动态规划

频繁查询子串是否回文：区间DP

字数统计: 1.2k字   |   阅读时长: 4分
, ,

摘要: 频繁查询子串是否回文，用区间DP预处理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在上一篇文章中，我们解决了分割回文串的问题，给定字符串 s，将其分为若干个回文子串，由于需要返回所有可能的分割方案，因此只能用回溯法。

本文我们解决分割回文串的第二个问题，还是将字符串 s 分割为若干回文子串，但只需要返回最少分割次数，这是一个优化的问题，可以考虑动态规划。

与 频繁查询子串是否回文：Manacher预处理后O(1)响应 中的情况一样，本题也是需要频繁查询子串是否是回文，处理方法也一样，先预处理一个二维数组 c，c[i][j] 表示子串 s[i..j] 是否是回文。

如果用 Manacher 算法预处理，用其中间结果的 p 数组来相应查询，可以 $O(n)$ 时间完成预处理，更直观的预处理方法是区间 DP，这也是在涉及到回文的问题中重用的算法，可以在 $O(N^{2})$ 的时间完成预处理。

如果算法在预处理外的部分的时间复杂度低于 $O(N^{2})$，将预处理的算法改为 Manacher 算法比较有意义，否则用区间 DP 处理也行，不影响整体的时间复杂度。

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

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

提示：

1
2
1 <= s.length <= 2000
s 仅由小写英文字母组成

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

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

示例 3：
输入：s = “ab”
输出：1

题解

算法：动态规划

定义 $dp[i]$ 表示前缀 s[0..i] 分割为回文子串最少可分成的部分数，比如如果前缀 s[0..2] = aab 最少可以分成 aa，b 2 个部分，于是 dp[2] = 2。这样定义的话 dp[n-1] + 1 就是最终答案。

初始值是前缀本身是回文的情况，即如果 s[0..i] 是回文，则 dp[i] = 1。比如单个字符的前缀 s[0] 本身就是回文，因此最少可分为 1 个部分，所以 dp[0] = 1。

接下来考虑状态转移方程。假设现在正在计算 dp[i]，如果 s[0..i] 是回文，则为初始值，直接取 dp[i] = 1 即可。否则进行以下推导。

考虑 $j = 1,\cdots,i$，若 s[j..i] 为回文，则可以将 s[j..i] 分割取出形成 1 个部分，之后要考虑剩下的 s[0..j-1] 可以分为几部分，这是重复子问题，其答案为 dp[j-1]，于是状态转移方程如下：

其中集合 $S$ 表示满足 $1 \leq j \leq i$ 且 s[j..i] 是回文的 $j$ 的集合。

这里我们需要频繁查询子串是否为回文，如果这步查询是 $O(1)$，则整体的时间复杂度为 $O(N^{2})$。

预处理：区间DP

为了响应频繁的子串是否为回文的查询，预处理一个二维数组 c，c[i][j] 表示子串 s[i..j] 是否为回文，若为回文则为 true，若不为回文则为 false。

由于单个字符是回文，因此 c[i][i] = true，空串也是回文，因此 c[i+1][i] = true。

如果子串 s[i..j] 长度大于 1，则看子串两个端点是否相等，若不相等则子串肯定不为回文；若相等，则继续看 s[i+1..j-1] 是否为回文。

上述过程就是一个区间 DP，也就是区间的两个端点构成了动态规划的阶段。

代码 (C++)

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
37
class Solution {
public:
    int minCut(string s) {
        if(s.empty()) 
            return 0;
        int n = s.size();
        vector<vector<bool> > c(n, vector<bool>(n, false));
        c[n - 1][n - 1] = true;
        for(int i = 0; i < n - 1; ++i)
        {
            c[i][i] = true;
            c[i + 1][i] = true;
        }
        for(int j = 1; j < n; ++j)
            for(int i = j - 1; i >= 0; --i)
                if(s[i] == s[j])
                    c[i][j] = c[i + 1][j - 1];

        vector<int> dp(n, 0);
        for(int i = 0; i < n; ++i)
        {
            if(c[0][i])
            {
                dp[i] = 1;
                continue;
            }
            int minx = INT_MAX;
            for(int j = 1; j <= i; ++j)
            {
                if(c[j][i])
                    minx = min(minx, dp[j - 1]);
            }
            dp[i] = minx + 1;
        }
        return dp[n-1] - 1;
    }
};
Share