【综合笔试题】难度 3/5，两遍 DP 的回文串分割题

题目描述

这是 LeetCode 上的「132. 分割回文串 II」，难度为「困难」。

Tag : 「回文串」、「线性 DP」

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

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

示例 1：

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

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

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

动态规划

如果在 131. 分割回文串 有使用到 DP 进行预处理的话。

这道题就很简单了，就是一道常规的动态规划题。

为了方便，我们约定所有下标从

开始。

即对于长度为

的字符串，我们使用

进行表示。

估计不少看过三叶题解的同学都知道，这样做的目的是为了减少边界情况判断，这本身也是对于「哨兵」思想的运用。

递推「最小分割次数」思路

我们定义

为将

这一段字符分割为若干回文串的最小分割次数，那么最终答案为

。

不失一般性的考虑

如何转移：

1. 从「起点字符」到「第

个字符」能形成回文串。那么最小分割次数为 0，此时有

；

1. 从「起点字符」到「第

个字符」不能形成回文串。此时我们需要枚举左端点

，如果

这一段是回文串的话，那么有

。

在

中满足回文要求的左端点位置

可能有很多个，我们在所有方案中取一个

即可。

快速判断「任意一段子串是否回文」思路

剩下的问题是，我们如何快速判断连续一段

是否为回文串，做法和昨天的 131. 分割回文串 一模一样。

PS. 在 131. 分割回文串，数据范围只有

，因此我们可以不使用 DP 进行预处理，而是使用双指针来判断是否回文也能过。但是该题数据范围为

（数量级为

），使用朴素做法判断是否回文的话，复杂度会去到

（计算量为

），必然超时。

因此我们不可能每次都使用双指针去线性扫描一遍

判断是否回文。

一个合理的做法是，我们先预处理出所有的

，

代表

这一段是否为回文串。

预处理

的过程可以用递推去做。

要想

，必须满足以下两个条件：

由于状态

依赖于状态

，因此需要我们左端点

是「从大到小」进行遍历；而右端点

是「从小到大」进行遍历。

因此最终的遍历过程可以整理为：右端点

一直往右移动（从小到大），在

固定情况下，左端点

在

在左边开始，一直往左移动（从大到小）。

代码：

class Solution {
    public int minCut(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        // g[l][r] 代表 [l,r] 这一段是否为回文串
        boolean[][] g = new boolean[n + 1][n + 1];
        for (int r = 1; r <= n; r++) {
            for (int l = r; l >= 1; l--) {
                // 如果只有一个字符，则[l,r]属于回文
                if (l == r) {
                    g[l][r] = true;
                } else {
                    // 在 l 和 r 字符相同的前提下
                    if (cs[l - 1] == cs[r - 1]) {
                        // 如果 l 和 r 长度只有 2；或者 [l+1,r-1] 这一段满足回文，则[l,r]属于回文
                        if (r - l == 1 || g[l + 1][r - 1]) {
                            g[l][r] = true;
                        }
                    }
                }
            }
        }

        // f[r] 代表将 [1,r] 这一段分割成若干回文子串所需要的最小分割次数
        int[] f = new int[n + 1];
        for (int r = 1; r <= n; r++) {
            // 如果 [1,r] 满足回文，不需要分割
            if (g[1][r]) {
                f[r] = 0;
            } else {
                // 先设定一个最大分割次数（r 个字符最多消耗 r - 1 次分割）
                f[r] = r - 1;
                // 在所有符合 [l,r] 回文的方案中取最小值
                for (int l = 1; l <= r; l++) {
                    if (g[l][r]) f[r] = Math.min(f[r], f[l - 1] + 1);
                }   
            }
        }

        return f[n];
    }
}

• 时间复杂度：

• 空间复杂度：

关于「如何确定状态定义」

有同学会对「如何确定 DP 的状态定义」有疑问，觉得自己总是定不下 DP 的状态定义。

首先，十分正常，不用担心。

DP 的状态定义，基本上是考经验的（猜的），猜对了 DP 的状态定义，基本上「状态转移方程」就是呼之欲出。

虽然大多数情况都是猜的，但也不是毫无规律，相当一部分是定义是与「结尾」和「答案」有所关联的。

例如本题定义

为以下标为

的字符作为结尾（结尾）的最小分割次数（答案）。

因此对于那些你没见过的 DP 模型题，可以从这两方面去「猜」。

Manacher（非重要补充）

如果你还学有余力的话，可以看看下面这篇题解。

提供了「回文串」问题的究极答案：Manacher 算法。

由于 Manacher 算法较为局限，只能解决「回文串」问题，远不如 KMP 算法使用广泛，不建议大家深究原理，而是直接当做「模板」背过。

背过这样的算法的意义在于：相当于大脑里有了一个时间复杂度为

的 api 可以使用，这个 api 传入一个字符串，返回该字符串的最大回文子串。

回文串问题的究极答案：Manacher 算法

如果觉得自己背不下来，也没有问题。事实上我还没有见过必须使用 Manacher 算法才能过的回文串题。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.132 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。