LeetCode：132.分割回文串II（DPJava）

目录

132. 分割回文串 II

题目描述：

实现代码与解析：

DP

原理思路：

---

132. 分割回文串 II 题目描述：

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= s.length <= 2000s 仅由小写英文字母组成 实现代码与解析： DP class Solution { public int minCut(String s) { int n = s.length(); boolean[][] d = new boolean[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(d[i], true); } for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { d[i][j] = s.charAt(i) == s.charAt(j) && d[i + 1][j - 1]; } } int[] f = new int[n]; Arrays.fill(f, 0x3f3f3f3f); for (int i = 0; i < n; i++) { if (d[0][i]) f[i] = 0; else { for (int j = 0; j < i; j++) { if (d[j + 1][i]) f[i] = Math.min(f[i], f[j] + 1); } } } return f[n - 1]; } } 原理思路：

        创建一个二维布尔数组 d 来记录字符串中任意子串是否为回文串。通过双重循环初始化 d 数组，先将所有元素初始化为 true，再通过动态规划的方式更新 d 数组，判断 s[i...j] 是否为回文串。

        创建一个一维整数数组 f，用于记录将字符串 s 的前 i 个字符分割成若干个回文子串所需的最少分割次数，初始值设为一个较大的数 0x3f3f3f3f。

        遍历字符串，若 s[0...i] 本身就是回文串，则 f[i] 为 0；否则，遍历 0 到 i-1 的所有 j，若 s[j+1...i] 是回文串，则更新 f[i] 为 f[j] + 1 和 f[i] 中的较小值。

        最后返回 f[n - 1]，即整个字符串分割成若干个回文子串所需的最少分割次数。